题目描述
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.
Follow up:
Could you solve it in linear time?
Example1:
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
Follow up:
- 1 <= nums.length <= 10^5
- 10^4 <= nums[i] <= 10^4
- 1 <= k <= nums.length
解题思路
- 参考
- 我们希望窗口内的数字是有序的，但是每次给新窗口排序又太费时了，所以最好能有一种类似二叉搜索树的结构，可以在 lgn 的时间复杂度内完成插入和删除操作，那么使用 STL 自带的 multiset 就能满足我们的需求，这是一种基于红黑树的数据结构，可以自动对元素进行排序，又允许有重复值，完美契合
- 遍历每个数字，即窗口右移，若超过了k，则需要把左边界值删除，这里不能直接删除 nums[i-k]，因为集合中可能有重复数字，我们只想删除一个，而 erase 默认是将所有和目标值相同的元素都删掉，所以我们只能提供一个 iterator，代表一个确定的删除位置，先通过 find() 函数找到左边界 nums[i-k] 在集合中的位置，再删除即可。
- 然后将当前数字插入到集合中，此时看若 i >= k-1，说明窗口大小正好是k，就需要将最大值加入结果 res 中，而由于 multiset 是按升序排列的，最大值在最后一个元素，我们可以通过 rbegin() 来取出
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
multiset<int> sets;
vector<int> res;
for(int i = 0; i < nums.size(); i++){
if(i >= k){ // 如果 i >= k 的话，证明需要移除左边的，不能直接进行溢出定值，需要一个迭代器
sets.erase(sets.find(nums[i - k]));
}
sets.insert(nums[i]); // 插入
if(i >= k - 1){
res.push_back(*sets.rbegin()); // set是按key升序排序的，那么最后一个rbegin指向的就是最大的元素
}
}
return res;
}
};
