数据结构题目
2020-06-15 / IOAOl   

面试题59 - I. 滑动窗口的最大值（LeetCode）（单调队列）

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

1
2
3
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7] 
在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> r;
        if(!nums.empty()){
            int max=nums[0];
            int maxindex=0;
            for(int i=0;i+k<=nums.size();i++){
                if(maxindex==i-1||i==0){	//第一个窗口或者是前一个窗口最大值已不在当前窗口
                    max=nums[i];
                    maxindex=i;
                    for(int j=0;j<k;j++){
                        if(max<nums[i+j]){
                            max=nums[i+j];
                            maxindex=i+j;
                        }
                    }
                }else{						//前一个窗口最大值还在当前窗口
                    if(max<nums[i+k-1]){
                        max=nums[i+k-1];
                        maxindex=i+k-1;
                    }
                }
                r.push_back(max);
            }
        }
        return r;
    }
};

思路：滑动窗口就是在前面加一个元素，后面减去一个元素，这里考虑了减去的元素是不是等于最大的元素，如果是，就找当前的窗口的最大元素，不是的话，说明前一窗口的最大元素仍在窗口，就将前一个窗口最大元素跟新加的元素比较，以确定当前窗口最大元素。

执行用时 :28 ms, 在所有 C++ 提交中击败了89.08%的用户

内存消耗 :15.7 MB, 在所有 C++ 提交中击败了100.00%的用户

缺点：在最大值在现有窗口被去除后找最大值的时间复杂度为O(k）

改进版本

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> ans;
       deque<int> deq;
       int n = nums.size();
       for (int i = 0; i < n; i++){
           while(!deq.empty() && nums[i] > nums[deq.back()]){
               deq.pop_back();
           }
           if (!deq.empty() && deq.front() < i - k + 1) deq.pop_front();
           deq.push_back(i);
           if (i >= k -1) ans.push_back(nums[deq.front()]);
       }
       return ans;

思路：维护一个单调队列，满足头为最大值，队列里的元素都为窗口元素。每次移动，检查添加元素是否大于尾元素，大于则去除，直到队列里只有比添加元素大的元素。之后检查头元素是不是不在当前窗口，不在则去除。最后头元素就是当前窗口最大的元素。

在窗口数大的时候优化明显,总体的时间复杂度是O(n)。

执行用时 :36 ms, 在所有 C++ 提交中击败了80.64%的用户

内存消耗 :16.3 MB, 在所有 C++ 提交中击败了100.00%的用户

本文链接：
https://ioaol.github.io/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E9%A2%98%E7%9B%AE.html