【死磕算法·栈和队列】滑动窗口问题-双端队列

题目要求：

有一个整型数组 arr 和一个大小为 w 的窗口从数组的最左边滑到最右边,窗口每次向右边滑一个位置。 返回一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的最大值。 以数组为[4,3,5,4,6,7]，w=3为例。因为第一个窗口[4,5]的最大值为5，第二个窗口[3,4]的最大值为5，第三个窗口[5,3]的最大值为5。第四个窗口[4,3]的最大值为4。第五个窗口[3,6]的最大值为6。第六个窗口[3,7]的最大值为7。所以最终返回[5,7]。

给定整形数组arr及它的大小n，同时给定w，请返回res数组。保证w小于等于n，同时保证数组大小小于等于500。

题目思路：

遍历数组，用双端队列的队首记录滑动窗口内最大值的位置。vector result 记录该滑动窗口内元素的最大值。

对于数组元素arr[i]：

若队列为空，将i加入队列尾部；

若队列不为空，将arr[i]和队列队尾元素x比较，若arr[i]大于x，将队列队尾元素弹出，直到arr[i]小于等于队尾元素或队列为空，将i加入队列尾部；

对于一个滑动窗口，如果队列的队头元素位置"过期"，也就是小于这个滑动窗最左端的位置（i-w+1），将队列的队首元素弹出，新队列的队首元素作为滑动窗口的最大值加入result中。

为什么比队尾小于或等于的元素要压入双端队列呢？

因为双端队列的队首记录着该滑动窗口最大元素的位置，要给它成为之后滑动窗口最大值的机会。

比队尾大的元素要让队列尾部元素（代表比当前值小的数组元素位置）不断弹出，直到该元素<=索引等于队列尾部值的数组元素。因为当前元素值比队尾元素索引位置的值要大，当前元素一定要在队列的前面，才能随着滑动窗口不断移动，队首元素不断过期弹出，到达队首，成为滑动窗口的最大值。

也就是要保证队列从队首到队尾，元素对应的数组值是递减的。

图解：

代码实现：

class SlideWindow {

public:

vector slide(vector arr,int n,int w) {

// write code here

deque s;

vector result;

for(int i = 0;i

if(s.empty())

s.push_back(i);

else{

while(!s.empty()&&arr[i]>arr[s.back()])

s.pop_back();

s.push_back(i);

}

}

result.push_back(arr[s.front()]);

for(int k = w;k

if(s.empty())

s.push_back(k);

else{

while(!s.empty()&&arr[k]>arr[s.back()])

s.pop_back();

s.push_back(k);

}

if(s.front()<=k-w)

s.pop_front();

result.push_back(arr[s.front()]);

}

return result;

}

};

注意点：

双端队列存储的是数组索引，在比较大小以及往result中加入当前滑动窗口最大值时，比较及加入的对象是具体的值，这里细心处理即可。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!