leetcode239丨滑动窗口最大值

Posted on

题目描述

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

返回 滑动窗口中的最大值 。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：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

示例 2：

1
2
输入：nums = [1], k = 1
输出：[1]

法一 暴力

可以直接扫描每个窗口，找到每个窗口的最大值，时间复杂度为0(K*N)，空间复杂度为O(1)，此方法易于实现，不多赘述。

在这种方法中，我们每次只往窗口中添加一个数、从窗口中删除一个数，却需要对窗口中所有数重新进行一遍比较，其中必然存在很大的优化空间。

法二 优先队列

频繁地对窗口中的数进行微小的更新，并维护一个最大值，这很容易让我们想到堆。我们可以维护一个大根堆，当窗口右边界从i滑动到i+1，我们就向堆中添加元素nums[i+1]，并删除元素nums[i-k+1]，然后输出堆顶元素。

但是，要从堆中查找到一个指定元素并删除并不容易。事实上，我们也不需要每次滑动窗口就马上将窗口外的元素删除，我们只关心窗口中最大的值，因此我们只需要在取出最大值时判断其是否在窗口内就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    priority_queue<pair<int,int>> stack;  // 堆中数据类型为一个整型对(nums[i],i)，其中i用来判断元素是否在窗口内
    vector<int> ans;
    for (int i = 0; i < k - 1; i++) {
        stack.emplace(nums[i], i);  // 将前k-1个元素压入堆中
    }        
    for (int i = k-1; i < nums.size(); i++) {  //从第k个元素开始，每将一个元素压入堆中，就取出一次窗口内的最大值
        stack.emplace(nums[i], i);  
        while (stack.top().second <= i - k) stack.pop();  // 如果堆顶元素在窗口外，则移出堆顶元素，直到堆顶在窗口内
        ans.push_back(stack.top().first);  // 此时堆顶元素即滑动窗口中的最大值
    }
    return ans;
}

每个元素都需要入堆一次，最坏情况下始终没有元素出堆，时间复杂度为O(NlogN)，空间复杂度为O(N)。

法三 单调队列

这个方法更加巧妙，一开始并没有想到。

在这个方法中，我们维护一个双端队列，用来存窗口中的元素。每扫描到一个元素nums[i]，我们进行如下处理：

  • 从队尾删除比nums[i]小的元素。在nums[i]被移出窗口前，比nums[i]小的元素不可能成为窗口内的最大值，而队列里已存在的元素必然先于nums[i]进入窗口，也将先于nums[i]移出窗口。因此队列中比nums[i]小的元素在被移出窗口前不可能成为最大的数了。
  • 从队首删除窗口外的元素。我们总是在队尾插入元素，因此队首的元素必然是最先进入队列的，也会是最先被移出窗口的。因此我们只需要从窗口移除元素，就可以保证队列内的元素总是在窗口内。

用以上方式维护队列，得到的队列必然满足：

  • 队列中的元素总是单调递减。因为根据第一条规则，队列中若存在q[i]<q[i+1]，那么在q[i+1]入队时，q[i]就应该被删除了。
  • 队列中的元素必然在窗口中。
  • 窗口中最大的元素必然在队列中。

因此，队列中最大的元素，也即窗口中最大的最大元素，必然在队列的队首。我们每次维护完队列，只需要输出队首元素就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    deque<int> q;
    vector<int> ans;
    for (int i = 0; i < nums.size(); i
        if (!q.empty() && i - q.front() >= k) q.pop_front();  // 队首元素在窗口外则出队
        if (q.empty() || nums[i] < nums[q.back()]) q.push_back(i);  // 如果nums[i]比队尾元素小则直接入队
        else{  // 否则将队尾小于nums[i]的元素删除后再入队
            while (!q.empty() && nums[i] >= nums[q.back()]){
                q.pop_back();
            }
            q.push_back(i);
        }
        if (i > k - 2) ans.push_back(nums[q.front()]);  // 从nums[k-1]开始窗口成形，每移动一次窗口都要获取一个最大值
    }
    return ans;

}

这种方法每个元素入队一次且最多出队一次，时间复杂度只有O(N)。