题解 | #滑动窗口的最大值#

滑动窗口的最大值

http://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788

窗口滑动的过程中需要队尾进队和队头出队,所以定义一个双端队列 deque 比较方便

for (i)

  1. 判断窗口的合法性

  2. 更新队列中滑动窗口的最大值,如果当前元素大于队尾元素,那么在当前窗口内的最大值就是当前元素,所以弹出队尾,直到遇到队列为空或者条件不成立为止

  3. 将当前下标入队

  4. 如果达到窗口的大小就记录答案,即队头元素对应的值就是当前滑动窗口的最大值

注意:

  • 队列中存放的是下标

  • 队头元素对应的值就是当前滑动窗口的最大值

全部评论

相关推荐

评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务