【LeetCode刷题记录】239. 滑动窗口最大值

本文主要是介绍【LeetCode刷题记录】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       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

示例 2：

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

提示：
$1 <= nums.length <= 10^5$
$10^4 <= nums[i] <= 10^4$
$1 <= k <= n u m s . l e n g t h$

思路

本题直接采用暴力法用 vector 存储每次的滑动窗口排序会运行超时，故需要采用单调递减数列进行优化。
一般采用双向队列 deque 实现单调队列。用该单调队列存储每次滑动窗口最大元素的索引值，将 deque 中的头元素与 $i - k$ 比较来控制滑动窗口大小，将尾元素与当前索引值对应元素比较大小，只保留较大值来保证单调递减。
PS：deque基本用法（转载自【C++ 十三】C++ deque容器）

插入元素：

push_back(value): 在deque的尾部插入一个元素。
push_front(value): 在deque的头部插入一个元素。

删除元素：

pop_back(): 删除deque的尾部元素。
pop_front(): 删除deque的头部元素。

访问元素：

front(): 返回deque的头部元素的引用。
back(): 返回deque的尾部元素的引用。

判断容器是否为空：

empty(): 如果deque为空，则返回true；否则返回false。

获取容器的大小：

size(): 返回deque中元素的个数。

清空容器：

clear(): 删除deque中的所有元素，使其变为空。

随机访问元素：

at(index): 返回位于指定索引位置的元素的引用，索引从0开始。
operator[](index): 返回位于指定索引位置的元素的引用。

代码

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {vector<int> v;// 利用双向队列创建单调递减队列，只存储元素索引// 保证滑动窗口内头元素是最大值的索引deque<int> dq;for (int i = 0; i < nums.size(); i++) {// 保证滑动窗口元素数始终等于kif (!dq.empty()  && dq.front() == i - k) {// 删头dq.pop_front();}// 遍历当前队列，保证单调递减while (!dq.empty() && nums[dq.back()] <= nums[i]) {// 删尾dq.pop_back();}dq.push_back(i); // 存储元素索引// 滑动窗口形成，开始存储索引对应值if (i >= k - 1) {v.push_back(nums[dq.front()]);}}return v;}
};