新轩的狗狗面巾

应该是TreeMap 吧。。。 排序和控制size全都有了

有了兄弟萌，这个题我觉得可能是Bucket Sort(counting sort) + sliding windows，主要节省时间在排序这块，排序时间从Onlogn 降到 On，但我没看过你的题，如果题是每次都要排序那就是从N * klogk降低到 N K。

yiliaobailiao 发表于 2020-7-30 09:39
楼主给的感觉不是最优解？用单调栈可以做到linear的时间复杂度。不过从这个看出来，最优并不一定是必须的 ...

层主能分享一下用单调栈的思路嘛~ 感觉似乎和Sliding Window Maximum 那道题的单调栈似乎还不太一样~ 谢谢~

affe 发表于 2020-8-21 14:47
层主能分享一下用单调栈的思路嘛~ 感觉似乎和Sliding Window Maximum 那道题的单调栈似乎还不太一样~ 谢 ...

跟那道题思路是一样的。那个滑动窗口的大小是固定的K，所以右端扫到新元素的时候，要判断跟窗口最左端之间的距离是不是超过K。这道题变成判断时间差是不是超过1小时就可以了（假定输入是按照时间戳排好序的）。

yiliaobailiao 发表于 2020-8-21 21:29
跟那道题思路是一样的。那个滑动窗口的大小是固定的K，所以右端扫到新元素的时候，要判断跟窗口最左端之 ...

恩恩，不过那道题没有用堆而是用了一个单调递增的栈来存所有可能的Max，我的意思是这道题有没有可能不用堆来存某一个窗口内的most viewed tweet，而是用一个单调的栈来做。

affe 发表于 2020-8-24 20:21
恩恩，不过那道题没有用堆而是用了一个单调递增的栈来存所有可能的Max，我的意思是这道题有没有可能不用 ...

两个题，感觉都是用单调递减的queue（比如python里面deque）来实现比较好，因为右边进，左边出。stack不太好，不容易左边pop。