题解 | #滑动窗口的最大值#
滑动窗口的最大值
http://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788
窗口滑动的过程中需要队尾进队和队头出队,所以定义一个双端队列 deque 比较方便
for (i)
-
判断窗口的合法性
-
更新队列中滑动窗口的最大值,如果当前元素大于队尾元素,那么在当前窗口内的最大值就是当前元素,所以弹出队尾,直到遇到队列为空或者条件不成立为止
-
将当前下标入队
-
如果达到窗口的大小就记录答案,即队头元素对应的值就是当前滑动窗口的最大值
注意:
-
队列中存放的是下标
-
队头元素对应的值就是当前滑动窗口的最大值
查看9道真题和解析