AcWing 79 滑動視窗的最大值

題目描述：

給定一個數組和滑動視窗的大小，請找出所有滑動視窗裡的最大值。

例如，如果輸入數組[2, 3, 4, 2, 6, 2, 5, 1]及滑動視窗的大小3,那麼一共存在6個滑動視窗，它們的最大值分别為[4, 4, 6, 6, 6, 5]。

注意：

• 資料保證k大于0，且k小于等于數組長度。

樣例

輸入：[2, 3, 4, 2, 6, 2, 5, 1] , k=3

輸出: [4, 4, 6, 6, 6, 5]
           

分析：

觀察樣例可以發現，解的出現順序是自左向右的。也就是說，随着視窗的右移，解要麼不變，要麼右移。考慮到解的單調性，這裡維護一個單調隊列來解決該問題。

1.目前解（滑動視窗最大值）是在視窗最左邊，也就是在隊頭，我們右移視窗時，便要将隊頭元素出隊來防止滑動視窗元素個數超過k。

2.新加入滑動視窗的元素值大于等于隊頭元素，為了維護隊單調遞減的性質，隻能将隊頭元素出隊。（後加入的元素呆的時間更長，是以新加入元素等于隊頭元素時依然出隊）

3.新加入的元素小于隊頭元素，此時不能直接入隊。比如上例的滑動視窗滑動到了6 2 5，到5時是小于6的，但大于2，此時隊列不單調。是以需要比較新加入元素與隊尾元素，若隊尾元素較小，則出隊。

考慮到以上三點，我們需要一個隊列在隊頭隊尾都能出隊，是以采用deque來解決。

注意：這裡為了維護滑動視窗的大小，我們入隊的是元素的下标而非值，使得操作更加友善。

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