239. Sliding Window Maximum

Posted on | Edited on | In , |

题目

https://leetcode.com/problems/sliding-window-maximum/description/

想法

初看觉得，直接扫一遍就好了，但是细想想，最大值是不断更新的，要各个状态下的最大值。

记录下最大的两个值看怎么样，不行，还是会更新

要不还是用DP试试，也不知道从何下手啊～

或许可以这样 先算出 1～k的最大值，再求2～k的是大值，再求2～k+1的最大值，再3～k+1最大值！
但是同样没有考虑重复，比如：5，3，3，2，2 (k = 3)

额，没有思路，如果完全用DP做，算出各段的最大值，真的好傻啊
算了，先这样做吧

放弃，看答案吧 这应该是一个很经典的问题，就算是记也要住

原理

Monotonic Queue
https://abitofcs.blogspot.com/2014/11/data-structure-sliding-window-minimum.html

答案

参考他人的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> dq;
        vector<int> ans;
        
        for (int i = 0; i < nums.size(); i++) {
            if (!dq.empty() && dq.front() == i - k)
                dq.pop_front();
            while(!dq.empty() && nums[i] > nums[dq.back()])
                dq.pop_back();
            dq.push_back(i);
            if (i >= k - 1)
                ans.push_back(nums[dq.front()]);
        }
        return ans;
    }
};

回顾

很经典的题目了

deque运用，用deque存索引是我没有想到的，这是一个值得学习的地方

还是注意分析表象背后的条件，一个个的往过移，那个一个较大的值出现，前边较小的就不再会成为最大值了，如代码中的：

1
2
while(!dq.empty() && nums[i] > nums[dq.back()])
    dp.pop_back();