滑动窗口最大值
给你一个整数数组, 有一个大小为 \(k\) 的滑动窗口从数组的最左侧移动到数组的最右侧. 你只可以看到在滑动窗口内的 \(k\) 个数字. 滑动窗口每次只向右移动一位.
考虑使用双端队列, 队列内存储数组的下标, 保证优先队列的队头为当前滑动窗口内最大元素所在数组的位置. 因为只需要关注最大值, 所以我希望这个双端队列应该是一个单调队列, 从队尾到队首单调递增. 假设现在给定数组前四个元素为 \(5, 4, 2, 1\), 窗口为 \(4\), 所以队列内的值为 \(1 , 2 , 4 , 5\), 左边为队尾, 右边为队首. 最新元素为 \(3\), 可以发现只要 \(3\) 在队列内, 那么 \(1, 2\) 就不可能是答案, 因此可以出队.
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
deque<int> q;
for (int i = 0; i < k; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
}
vector<int> ans = {nums[q.front()]};
for (int i = k; i < nums.size(); ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
while (q.front() <= i - k) {
q.pop_front();
}
ans.push_back(nums[q.front()]);
}
return ans;
}