snap 电面

zhc · 2019-10-11 15:20:12

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

求Sliding Window里

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

时求下minimum)

nlackx · 2019-10-30 08:22:32

O(N)的做法就是维护2个 Deque，分别是一个单调递增，另一个单调递减。每次先根据window维护 deques，然后用两个 top 来算答案。

wtcupup · 2019-10-11 15:26:10

用两个heap吗？

zhc · 2019-10-11 15:31:46

wtcupup 发表于 2019-10-11 15:26
用两个heap吗？

用heap不是最好的解法. 可以看看LC那道题dicussion里得票最多的答案。

torez · 2019-10-11 19:54:25

zhc 发表于 2019/10/11 15:31:46
用heap不是最好的解法. 可以看看LC那道题dicussion里得票最多的答案。

或者用两个treemap？heap remove是O(n)而treemap是O(logn)