Ex59-I 滑动窗口的最大值

题目描述

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

解题思路

使用一个辅助的双端队列indexs，存放的nums中的数字的index。

1. 前k的数字，取最大的数字放到indexs中。
2. k以后的数字，仍然取最大的数字放到indexs中，并且淘汰不在滑动窗口范围之内的数字。

代码

class Solution {
 public:
  std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
    std::vector<int> maxs;
    if (nums.size() <= 0 || k <= 0) return maxs;
    std::deque<int> indexs;
    for (int i = 0; i < k; ++i) {
      while (!indexs.empty() && nums[i] >= nums[indexs.back()])
        indexs.pop_back();
      indexs.push_back(i);
    }
    for (int i = k; i < nums.size(); ++i) {
      maxs.push_back(nums[indexs.front()]);
      while (!indexs.empty() && nums[i] >= nums[indexs.back()])
        indexs.pop_back();
      if (!indexs.empty() && indexs.front() <= i - k) indexs.pop_front();
      indexs.push_back(i);
    }
    maxs.push_back(nums[indexs.front()]);
    return maxs;
  }
};

结果

执行结果：通过

执行用时：40 ms, 在所有 C++ 提交中击败了69.51%的用户

内存消耗：16.1 MB, 在所有 C++ 提交中击败了20.00%的用户