#栈与队列 #滑动窗口最大值

sliding-window-maximum.cpp

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        //        a          b
        //      5 1 2      1 5 2
        // [1]  5 * 2      * 5 2

        //      5 1 3      5 1 0
        // [2]  5 1        5 1    

        vector<int> result;
        deque<int> win; // in decrese   
        for (int i = 0; i < k; ++i) {
            // pop values befor push
            while (!win.empty() && win.back() < nums[i])
                win.pop_back(); // [2a]
            win.push_back(nums[i]);
        }
        result.push_back(win.front());

        for (int i = k; i < nums.size(); ++i) {
            // window is full
            if (!win.empty() && win.front() == nums[i-k])
                win.pop_front(); // [1a]

            // pop values befor push
            while (!win.empty() && win.back() < nums[i])
                win.pop_back(); // [2a]
            win.push_back(nums[i]);
            
            // the deque is decrese
            result.push_back(win.front());
        }
        return result;
    }
};