https://leetcode-cn.com/problems/sliding-window-maximum/
暴力
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
int n = nums.size();
int left = 0;
for (int right = 0; right < n; right++) {
if (right - left + 1 < k) {
continue;
}
int max_value = nums[right];
for (int i = right; i > right - k; i--) {
max_value = max(max_value, nums[i]);
}
res.push_back(max_value);
left++;
}
return res;
}
会超时哦。
维护一个大小为k的排序结构
我们希望窗口内的数字是有序的，但是每次给新窗口排序又太费时了，所以最好能有一种类似二叉搜索树的结构，可以在 lgn 的时间复杂度内完成插入和删除操作，那么使用 STL 自带的 multiset 就能满足我们的需求，这是一种基于红黑树的数据结构，可以自动对元素进行排序，又允许有重复值，完美契合。
所以我们的思路就是，遍历每个数字，即窗口右移，若超过了k，则需要把左边界值删除，这里不能直接删除 nums[i-k]，因为集合中可能有重复数字，我们只想删除一个，而 erase 默认是将所有和目标值相同的元素都删掉，所以我们只能提供一个 iterator，代表一个确定的删除位置，先通过 find() 函数找到左边界 nums[i-k] 在集合中的位置，再删除即可。然后将当前数字插入到集合中，此时看若 i >= k-1，说明窗口大小正好是k，就需要将最大值加入结果 res 中，而由于 multiset 是按升序排列的，最大值在最后一个元素，我们可以通过 rbegin() 来取出
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
multiset<int> st;
int n = nums.size();
for (int i = 0; i < n; 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;
}
单调队列
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
deque<int> q;
int n = nums.size();
for (int i = 0; i < n; i++) {
if (i>=k) {
//need delete
if (!q.empty() && q.front() == i-k) {
q.pop_front();
}
}
//insert
while (!q.empty() && nums[q.back()] <= nums[i]) q.pop_back();
q.push_back(i);
//output window's max value
if (i >= k-1) {
res.push_back(nums[q.front()]);
}
}
return res;
}
https://leetcode-cn.com/problems/sliding-window-maximum/solution/dan-diao-dui-lie-by-labuladong/
