1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq;
vector<int> ret;
for(int i = 0; i < nums.size(); ++i)
{
if(!dq.empty() && dq.front() < i - k + 1)
dq.pop_front();
while(!dq.empty() && nums[dq.back()] < nums[i])
dq.pop_back();
dq.push_back(i);
if(i >= k - 1)
ret.push_back(nums[dq.front()]);
}
return ret;
}
};
|
使用双向序列，先加入的在序列头，后加入的在序列尾。当序列头中坐标小于i-k+1时，这个元素对于目前的窗口已经没用了，将其舍弃掉。对于其他的元素，从尾部移掉所有小于当前值的元素，因为对于a[x] < a[i] && x < i，后面的窗口可以使用a[i]而不是a[x]。由此一来序列头永远都是当前窗口最大项。
为什么从尾部移除小于当前值的元素而不是从头部呢？ > 只需要想清楚要移除的是a[x] < a[i] && x < i，因此在插入一个元素前把前面的无用项全都丢了再插入，当然是从后面开始往前删。a[x] > a[i] && x < i的元素对后面是有用的
1620305144539.png