# [LeetCode] Sliding Window Maximum 滑动窗口最大值

+关注继续查看

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[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


Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, 1 ≤ k ≤ input array's size.

Could you solve it in linear time?

Hint:

1. How about using a data structure such as deque (double-ended queue)?
2. The queue size need not be the same as the window’s size.
3. Remove redundant elements and the queue should store only elements that need to be considered.

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

9688 0
[leetcode/lintcode 题解] 算法面试真题详解：数组中最大的差值
[leetcode/lintcode 题解] 算法面试真题详解：数组中最大的差值
137 0

11374 0

13408 0

11676 0
C++ STL之min_element()与max_element（）（取容器中的最大最小值）
min_element()和max_element 头文件：#include 作用：返回容器中最小值和最大值。max_element(first,end,cmp);其中cmp为可选择参数!   闲言少叙，上代码，一看就懂： 1 #include 2 #include ...
1344 0

7086 0
+关注

2107

1103

《2021云上架构与运维峰会演讲合集》

《零基础CSS入门教程》

《零基础HTML入门教程》