LeetCode239.滑动窗口最大值

给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。

进阶：
你能在线性时间复杂度内解决此题吗？

示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sliding-window-maximum

1.暴力，时间复杂度O(nk)

对于长度为n的序列，一共回有n-k+1个窗口，所以时间复杂度为O(k*(n-k+1))，如果n过大的话很明显会超时。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        int n = nums.size();
        if(!n) return ans;
        if(!k) return ans;
        for(int i = 0; i<n-k+1; i++){
            int t = INT_MIN;
            for(int j = i; j<i+k; j++){
                t = max(t,nums[j]);
            }
            ans.push_back(t);
        }

        return ans;
    }
};

2.单调队列，时间复杂度O(n)

维护一个队列(双向队列)，队列中的元素具有单调性(单调递减)，为什么要这样做呢，举这样一个例子，对于序列3,-1,-3,5,4来说(k=3)，如果当前窗口是[3 ,-1 , -3]，很明显，最大值是3，接着移动窗口，3被弹出(双向队列，弹出为O(1))，当前窗口是[-1, -3, 5]，考虑这样一个问题，-1和-3对之后的答案有没有贡献？答案是没有，因为它们都比5要小，而且-1和-3弹出队列的时间是早于5的，所以它们一定不是答案，我们在让5进入队列之前需要将这些对之后没有贡献的值全部清除，所以单调递减的意义就凸显出来，因为窗口中新加入的值虽然在当前是最小的，但是它对于除了它之前的那些数之外，它可能是后面要进入的那些数中的最大值，比如[7, 4, 3, 2, 1 ,1]中的2，虽然它在前面很小，但是到了[2, 1, 1]这个窗口，他就是老大，所以我们要维护的队列是单调递减的，队头元素就是每个窗口的最大值。

因为每个值只会进出队列一次，所以时间复杂度是线性的。

class Solution {
public:
   vector<int> maxSlidingWindow(vector<int>& nums, int k) {
       vector<int> ans;
       int n = nums.size();
       if(!n) return ans;
       if(!k) return ans;
       int q[100010];
       memset(q,0,sizeof q);
       int hh =0, tt = -1;
       for(int i = 0; i<n; i++){
           //判断队头是否滑出窗口
           if(hh<=tt && i-k+1>q[hh]) hh++;
           //滑一步，将队列中比新入队数小的都删掉，保持队列的单调性
           while(hh<=tt && nums[q[tt]]<=nums[i]) tt--;
           q[++tt] = i;
           if(i+1>=k) ans.push_back(nums[q[hh]]);
       }

       return ans;
   }
};