Snapchat电面面经

很简单，实现

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

stephaniede 发表于 2016-8-5 06:30
Push的时候比mini小的话压入2*value －miniValue，这是什么原因？压入stack的不就不是当前值了？ 虽然你m ...

如何这个value比当前的minValue 小，那么压入2*value - minValue， 比value 小，因为这个value会成为下一个minValue，所以可以恢复回来。

补充内容 (2016-8-5 06:32):
如果*

stephaniede 发表于 2016-8-5 05:24
LZ用的two stacks实现的吗？ 有没有更加省空间的

constant memory 可以实现，用miniValue记录mini，push时候和mini比较 要不要更新，如果比mini小的话，压入的数据写成2*value - miniValue， 并更新minValue 为新的min；Pop的时候一样

羡慕啊，楼主有follow up吗

LZ用的two stacks实现的吗？ 有没有更加省空间的

blackrose 发表于 2016-8-4 14:37
constant memory 可以实现，用miniValue记录mini，push时候和mini比较 要不要更新，如果比mini小的话，压 ...

Push的时候比mini小的话压入2*value －miniValue，这是什么原因？压入stack的不就不是当前值了？ 虽然你mini随之更新了。

blackrose 发表于 2016-8-4 15:32
如何这个value比当前的minValue 小，那么压入2*value - minValue， 比value 小，因为这个value会成为下一 ...

懂了懂了。这个方法不错～～ 多谢啊～

stephaniede 发表于 2016-8-5 06:34
懂了懂了。这个方法不错～～ 多谢啊～

我在discuss里面还看到了一个解法也是constant space！ 就是如果push 当前值小于最小值 就把最小值也push进去 然后更新最小值 如果pop的时候如果当前值等于最小值 就多pop一次 更新min就是之前的最小值~~