239. 滑动窗口最大值

239. 滑动窗口最大值 #

链接 #

239. 滑动窗口最大值

题目 #

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

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

示例 1：

输入：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：

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

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104
  • 1 <= k <= nums.length

解答 #

class Solution {
 public:
  vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    int n = static_cast<int>(nums.size());
    deque<int> q;
    // 为什么是 n - k + 1
    // | data | data |
    //        k      n
    //    因为 n 指向数组末尾
    //        k 指向窗口末尾
    //        n - k 得到 k 后面可以移动的位数
    //        + 1 是因为 k 自身前面的数据
    // 也可以考虑极端情况 k = 1, 那么 retsize 必然等于 n
    std::vector<int> ret(n - k + 1);
    for (int i = 0; i < n; i++) {
      // 定义左闭右开的右端点这种指针为自然指针，要得到下标还要 - 1
      // 定义左闭右开的左端点这种指针为索引指针，是计算机中最自然的指针
      // 同类指针之间相减可以直接得到距离（可以和自然指针比较）/新的索引
      // 而不同类相减需要转换，通过 +1 or -1
      // 同类指针相减得到的指针不包含其类型的右端点，所以要计算个数还要 + 1
      // 从而算上右端点

      // 为什么是 i - k + 1
      // 可以看成 i - (k - 1)
      // 因为我们要计算窗口的开始索引，因此需要把 k 这个自然指针转换为索引指针

      int start = i - k + 1;
      while (!q.empty() && i - q.front() >= k) {
        // 确保窗口大小
        q.pop_front();
      }
      while (!q.empty() && nums[q.back()] <= nums[i]) {
        q.pop_back();
      }
      q.push_back(i);
      // start < 0 时窗口尚未建立起来
      if (start >= 0) {
        ret[start] = nums[q.front()];
      }
    }
    return ret;
  }
};

当解决滑动窗口最大值问题时，可以通过使用一个双端队列（deque）来维护窗口内的元素。我们可以将队列中的元素按照降序排列，以便快速找到窗口内的最大值。

让我们通过一个例子来说明这个思路。假设我们有一个数组 ([1, 3, -1, -3, 5, 3, 6, 7])，窗口大小为 3。我们可以按照以下步骤进行操作：

  1. 初始时，窗口内的元素为 ([1, 3, -1])。我们可以使用一个双端队列来存储窗口内的元素，并保持队列中的元素降序排列。在这个例子中，初始时队列为空，我们将依次将元素加入队列。

    • 步骤1：将元素1加入队列，队列变为 ([1])
    • 步骤2：将元素3加入队列，队列变为 ([3, 1])
    • 步骤3：将元素-1加入队列，队列变为 ([3, 1, -1])

  2. 窗口开始滑动。我们需要在每次滑动窗口时更新队列，以确保窗口内的元素按照降序排列。

    • 步骤4：窗口滑动到位置1，此时窗口内的元素为 ([3, -1, -3])。我们需要将队列中小于当前元素的值都移除，然后将当前元素加入队列。
      • 移除队列中小于3的元素，队列变为 ([3])
      • 将元素-3加入队列，队列变为 ([3, -3])
    • 步骤5：窗口滑动到位置2，此时窗口内的元素为 ([-1, -3, 5])。我们同样需要更新队列。
      • 移除队列中小于5的元素，队列变为 ([5])
      • 将元素5加入队列，队列变为 ([5, 5])
    • 步骤6：窗口滑动到位置3，窗口内的元素为 ([-3, 5, 3])。更新队列。
      • 移除队列中小于3的元素，队列变为 ([5, 3])
      • 将元素3加入队列，队列变为 ([5, 3, 3])
    • 步骤7：窗口滑动到位置4，窗口内的元素为 ([5, 3, 6])。更新队列。
      • 移除队列中小于6的元素，队列变为 ([6])
      • 将元素6加入队列，队列变为 ([6, 6])
    • 步骤8：窗口滑动到位置5，窗口内的元素为 ([3, 6, 7])。更新队列。
      • 移除队列中小于7的元素，队列变为 ([7])
      • 将元素7加入队列，队列变为 ([7, 7])

  3. 在每次滑动窗口时，队列的第一个元素即为当前窗口的最大值。在上述例子中，最终得到的最大值序列为 ([3, 3, 5, 5, 6, 7])。

当给定数组 ([5, 3, 4, 1]) 和窗口大小 (k = 3) 时，让我们按照之前的思路来计算滑动窗口的最大值。

  1. 初始时，窗口内的元素为 ([5, 3, 4])。我们使用一个双端队列来维护窗口内的元素，并保持队列中的元素按降序排列。

    • 步骤1：将元素5加入队列，队列变为 ([5])
    • 步骤2：将元素3加入队列，队列变为 ([5, 3])
    • 步骤3：将元素4加入队列，队列变为 ([5, 4, 3])

  2. 窗口开始滑动：

    • 步骤4：窗口滑动到位置1，此时窗口内的元素为 ([3, 4, 1])。我们需要更新队列。
      • 移除队列中小于3的元素，队列变为 ([3])
      • 将元素1加入队列，队列变为 ([3, 1])
    • 步骤5：窗口滑动到位置2，此时窗口内的元素为 ([4, 1])。更新队列。
      • 移除队列中小于4的元素，队列变为 ([4])
      • 将元素1加入队列，队列变为 ([4, 1])

  3. 在每次滑动窗口时，队列的第一个元素即为当前窗口的最大值。在上述例子中，最终得到的最大值序列为 ([5, 4, 4])。

Edit Edit this page