Leetcode题解剑指 Offer 59 - I. 滑动窗口的最大值

PROBLEM

难度困难

MY ANSWER

使用优先队列维护滑动窗口，存储值和索引，时间复杂度O(nlogn)，空间复杂度O(n)。

BETTER SOLUTION

使用deque构造单调栈维护滑动窗口，保存了从最大值开始的递减序列。时间复杂度O(n)，空间复杂度O(k)。

每次滑动，出窗元素若是最大值，则单调栈栈底出栈。然后检查栈顶是否大于入窗元素，若小于则出栈，以此来维护单调栈的单调性。最后将入窗元素入栈，栈底作为当前窗口的最大值加入到结果中。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> tmp;
        vector<int> res;
        if(nums.empty()) {
            return res;
        }
        tmp.push_back(nums[0]);
        for(int i = 1; i < k; i++) {
            while(tmp.size() && tmp.back() < nums[i]) {
                tmp.pop_back();
            }
            tmp.push_back(nums[i]);
        }
        res.push_back(tmp.front());
        for(int i = 0; i < nums.size() - k; i++) {
            if(nums[i] == tmp.front()) {
                tmp.pop_front();
            }
            while(tmp.size() && tmp.back() < nums[i+k]) {
                tmp.pop_back();
            }
            tmp.push_back(nums[i+k]);
            res.push_back(tmp.front());
        }
        return res;
    }
};

SUMMARY

复习单调栈的用法，当需要获得最大/最小值且有序的信息，考虑使用单调栈。