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. Return the max sliding window.
Example:
Input: nums =[1,3,-1,-3,5,3,6,7], and k = 3
Output:[3,3,5,5,6,7]
Explanation:
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
Note:
You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array.
Follow up:
Could you solve it in linear time?
Hint:
- How about using a data structure such as deque (double-ended queue)?
The queue size need not be the same as the window’s size.
Remove redundant elements and the queue should store only elements that need to be considered.
这道题给定了一个数组，还给了一个窗口大小k，让我们每次向右滑动一个数字，每次返回窗口内的数字的最大值。难点就在于如何找出滑动窗口内的最大值（这不废话么，求得不就是这个），那么最狂野粗暴的方法就是每次遍历窗口，找最大值呗，OJ 说呵呵哒，no way！我们希望窗口内的数字是有序的，但是每次给新窗口排序又太费时了，所以最好能有一种类似二叉搜索树的结构，可以在 lgn 的时间复杂度内完成插入和删除操作，那么使用 STL 自带的 multiset 就能满足我们的需求，这是一种基于红黑树的数据结构，可以自动对元素进行排序，又允许有重复值，完美契合。所以我们的思路就是，遍历每个数字，即窗口右移，若超过了k，则需要把左边界值删除，这里不能直接删除 nums[i-k]，因为集合中可能有重复数字，我们只想删除一个，而 erase 默认是将所有和目标值相同的元素都删掉，所以我们只能提供一个 iterator，代表一个确定的删除位置，先通过 find() 函数找到左边界 nums[i-k] 在集合中的位置，再删除即可。然后将当前数字插入到集合中，此时看若 i >= k-1，说明窗口大小正好是k，就需要将最大值加入结果 res 中，而由于 multiset 是按升序排列的，最大值在最后一个元素，我们可以通过 rbeng() 来取出，参见代码如下：
解法一：
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
multiset<int> st;
for (int i = ; i < nums.size(); ++i) {
if (i >= k) st.erase(st.find(nums[i - k]));
st.insert(nums[i]);
if (i >= k - ) res.push_back(*st.rbegin());
}
return res;
}
};
我们也可以使用优先队列来做，即最大堆，不过此时我们里面放一个 pair 对儿，由数字和其所在位置组成的，这样我们就可以知道每个数字的位置了，而不用再进行搜索了。在遍历每个数字时，进行 while 循环，假如优先队列中最大的数字此时不在窗口中了，就要移除，判断方法就是将队首元素的 pair 对儿中的 second（位置坐标）跟 i-k 对比，小于等于就移除。然后将当前数字和其位置组成 pair 对儿加入优先队列中。此时看若 i >= k-1，说明窗口大小正好是k，就将最大值加入结果 res 中即可，参见代码如下：
解法二：
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
priority_queue<pair<int, int>> q;
for (int i = ; i < nums.size(); ++i) {
while (!q.empty() && q.top().second <= i - k) q.pop();
q.push({nums[i], i});
if (i >= k - ) res.push_back(q.top().first);
}
return res;
}
};
题目中的 Follow up 要求我们代码的时间复杂度为 O(n)。提示我们要用双向队列 deque 来解题，并提示我们窗口中只留下有用的值，没用的全移除掉。果然 Hard 的题目我就是不会做，网上看到了别人的解法才明白，解法又巧妙有简洁，膜拜啊。大概思路是用双向队列保存数字的下标，遍历整个数组，如果此时队列的首元素是 i-k 的话，表示此时窗口向右移了一步，则移除队首元素。然后比较队尾元素和将要进来的值，如果小的话就都移除，然后此时我们把队首元素加入结果中即可，参见代码如下：
解法三：
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
deque<int> q;
for (int i = ; 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 - ) res.push_back(nums[q.front()]);
}
return res;
}
};
类似题目：
Minimum Window Subsequence
Min Stack
Longest Substring with At Most Two Distinct Characters
Paint House II
参考资料：
https://leetcode.com/problems/sliding-window-maximum/
https://leetcode.com/problems/sliding-window-maximum/discuss/65936/My-Java-Solution-Using-PriorityQueue
https://leetcode.com/problems/sliding-window-maximum/discuss/65884/Java-O(n)-solution-using-deque-with-explanation
LeetCode All in One 题目讲解汇总(持续更新中...)
