leetcode 239 单调队列 需要一些记忆

张开发
• 2026/4/18 11:13:31 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

leetcode 239 单调队列 需要一些记忆
滑动窗口最大值刚看到一种朴素的思想扑面而来就是优先队列map是可以解决这个问题的就是空间复杂度稍高并且不优雅并且 O(NlogN)一种更为优雅的做法是单调队列这个就稍微比较考验技巧了如果是第一次听说最好还是全文背诵。。。这里存下标的原因是由于我们可能会把队里的元素删光所以不知道最前面的是不是该被删的老的还是新放的放下标的处理会更为简单代码如下typedefvectorintV;classSolution{public:vectorintmaxSlidingWindow(vectorintnums,intk){dequeintq;V ans;intnnums.size();for(inti0;in;i){intnumnums[i];while(q.size()0nums[q.back()]num)q.pop_back();while(q.size()0q.front()i-k)q.pop_front();q.push_back(i);if(ik-1)ans.push_back(nums[q.front()]);}returnans;}};

更多文章