Sliding Window Maximum

解题思路

  1. 说实话，没专门学过，很难想到单调队列这种数据结构。。

  2. 在思考过程中，其实是想到要构造一个队列来维护当前有序集合，我想的是 LRU 那种做法了，就差一步，差的就是要意识到当前元素大于队尾元素时，队尾元素可以直接舍弃，这样，用链表也能实现单调队列。

  3. 我会在 Algorithm101 中记录单调队列这种数据结构。

代码

// 单调队列
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> m;
        vector<int> res;
        // 这里面有个很好玩的地方
        // i 不能声明为 size_t 类型
        // 因为后面有计算 i-k，k 为 int，结果永远不会小于 0
        for (int i = 0; i < nums.size(); ++i) {
            while (!m.empty() && nums[m.front()] < nums[i]) {
                m.pop_front();
            }
            m.push_front(i);
            if (i >= k-1) {
                res.push_back(nums[m.back()]);
            }
            if (m.back() <= i-k+1) {
                m.pop_back();
            }
        }
        return res;
    }
};