LeetCode 239 Sliding Window Maximum
概述
https://leetcode.com/problems/sliding-window-maximum/
直接法
题目很好理解，让找滑动窗口内的最大值，暴力算法 O(nk)，其中 n 是元素个数，k 是窗口大小。
暴力算法每次都遍历窗口内的所有元素，找出其最大值。 但是当前窗口与上一个窗口相比就增添了一个数，并减少了一个数， 如果每次都遍历一遍的话，显然重复计算的情况很严重。
为了避免重复计算，那我们就要用额外的数据结构来存储一些关键的信息，这里很自然地联想到队列。
遍历所有元素已经是 O(n) 了，那么接下来我们对队列进行操作找当前窗口下的最大值时的操作只能是 O(1)。
当队列的最前端或最后端就是我们要找的值时，直接 O(1) 就可以拿到这个值。
因此我们需要把当前窗口下的最大值搞到队列的某一端。
对于双端队列来说，哪一端都无所谓，这里我们让队列的最前端存当前窗口下的最大值。
什么时候把最前端的值弹出呢？当最前端的元素不在当前窗口内时我们应该把其弹出。
什么时候压入元素呢？对于每一个元素，当遍历到其时我们都必须压入。为什么？ 因为我们遍历该元素时无法获知后面的元素的值，有可能在窗口 [i, i+k) 中该值就是最大值了（i 为当前元素的索引）。
压入之前我们要做什么吗？我们需要把当前队列的最后的一个元素与当前元素作比较，如果其小于当前元素， 那我们需要把其弹出，不仅如此，我们还要继续弹出队列的后端元素，直到后端的元素不小于当前元素为止。
为什么？设这些元素的索引为 j，因为其值小于 nums[i]，那其只可能在右端在范围 [j, i-k] 内的某个窗口中做最大值， 但是我们正在处理的窗口是 (i-k, i]，右端是 i，在该范围的右面，也就是说我们已经处理过右端在范围 (j-k, i-k] 内的所有窗口了， 亦即这些值已经没用了，因此可以删去。
之后再把当前元素压入，此时队列的最前端一定是窗口 (i-k, i] 内的最大值。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> queue;
vector<int> ans;
for (int left = 0; left < nums.size(); ++left) {
// As the window move on, element nums[left-k] will be outdated.
if (!queue.empty() && queue.front() == left - k) queue.pop_front();
// Now we are ready to push our new element nums[left]'s index into the queue.
// But before that, we should clear elements which is smaller then nums[left].
// Why? Because if nums[left] is bigger then nums[i],
// there will be no way for nums[i] be selected as the max number in range (left-k, left]
while (!queue.empty() && nums[queue.back()] < nums[left]) queue.pop_back();
// Now push the index into our queue.
queue.push_back(left);
// Okay, now nums[queue.front()] mush be the max number in range (left-k, left]
if (left - k + 1 >= 0) ans.push_back(nums[queue.front()]);
}
return ans;
}
};
以上为 2020 年时做这道题的笔记。
单调队列
https://labuladong.gitee.io/algo/2/20/52/
当窗口右移时，我们需要弹出最左侧的值，压入新值，还得使得该值处在合理的大小位置中。
需要注意的是，当新值进入，比其小即相同的值就被彻底抑制了，因此这些值就可以删除了。
deque 里存索引而非存值。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ans;
deque<int> d;
for (int i = 0; i < nums.size(); i ++) {
while (!d.empty() && nums[d.back()] <= nums[i]) {
d.pop_back();
}
d.push_back(i);
if (d.front() + k <= i) d.pop_front();
if (i >= k - 1) ans.push_back(nums[d.front()]);
}
return ans;
}
};