239.Sliding Window Maximum
2021-03-09 13:28
标签：nbsp tis top vector cto res pair int pos 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. 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? 难度系数 Hard 解法一：通过STL中的multiset解决，对元素自动排序，且允许有重复值 解法二：通过优先队列实现，将数值和下标均放到优先队列中，优先队列会对按照数值大小堆排，只需要保证数值在窗口中即可。 解法三：双端队列添加下标，下标对应的元素是由front到back递减的 239.Sliding Window Maximum 标签：nbsp tis top vector cto res pair int pos 原文地址：https://www.cnblogs.com/AntonioSu/p/12748842.html题目描述
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] 7class Solution {
public:
vectorint> maxSlidingWindow(vectorint>& nums, int k) {
vectorint> res;
//允许有重复的元素，如若删除某个元素，则所有相同值的元素均被删除
multisetint> st;
for (int i = 0; i i) {
//从开始查找，找到则返回位置，并删除
if (i >= k) st.erase(st.find(nums[i - k]));
st.insert(nums[i]);
if (i >= k - 1) res.push_back(*st.rbegin());
}
return res;
}
};
class Solution {
public:
vectorint> maxSlidingWindow(vectorint>& nums, int k) {
vectorint> res;
priority_queue
class Solution {
public:
vectorint> maxSlidingWindow(vectorint>& nums, int k) {
vectorint> res;
//双向队列
dequeint> q;
for (int i = 0; i i) {
//说明此时队列中的元素长度大于k，或者是这个元素，已经不在窗口中了，故而删除
if (!q.empty() && q.front() == i - k) q.pop_front();
//队列中的的下标对应nums中的值由front到back是递减的
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;
}
};
文章标题：239.Sliding Window Maximum
文章链接：http://soscw.com/index.php/essay/62300.html