• 困难
  • 中等
  • 简单

    题目描述

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

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

来源，leetcode 每日一题 239. 滑动窗口数组

示例：

  1. 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
  2. 输出：[3,3,5,5,6,7]
  3. 解释：
  4. 滑动窗口的位置                最大值
  5. ---------------               -----
  6. [1  3  -1] -3  5  3  6  7       3
  7.  1 [3  -1  -3] 5  3  6  7       3
  8.  1  3 [-1  -3  5] 3  6  7       5
  9.  1  3  -1 [-3  5  3] 6  7       5
  10.  1  3  -1  -3 [5  3  6] 7       6
  11.  1  3  -1  -3  5 [3  6  7]      7

解题思路

  1. 暴力法：每次取出k个数字，然后遍历获得最大值，239. 滑动窗口数组 - 图1。
  2. 大根堆（优先队列）：将k个大小的数组，构建成一个优先队列，每次都弹出不在窗口中的值
  3. 单调队列：当每个值加入队列前，先弹出当前比它小的值，同时，弹出不在窗口中的值。

    代码

    大根堆法

    ```cpp class Solution { public: vector maxSlidingWindow(vector& nums, int k) {
     int n = nums.size();
 priority_queue<pair<int, int>> q;
 for (int i = 0; i < k; ++i) {
     q.emplace(nums[i], i);
 }
 vector<int> ans = {q.top().first};
 for (int i = k; i < n; ++i) {
     q.emplace(nums[i], i);
     while (q.top().second <= i - k) {
         q.pop();
     }
     ans.push_back(q.top().first);
 }
 return ans;
    } };
<a name="6FidE"></a>
### 单调队列法
```cpp
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        for (int i = 0; i < k; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
        }

        vector<int> ans = {nums[q.front()]};
        for (int i = k; i < n; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
            while (q.front() <= i - k) {
                q.pop_front();
            }
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};