滑动窗口的最大值
关键词:滑动窗口最值、deque
题目描述
给定一个数组 nums
和滑动窗口的大小 k
,请找出所有滑动窗口里的最大值。
示例 1:
1 |
|
解法
解法一:
思路:
- 这种滑动窗口的最值问题,一般可以考虑使用队列或者栈来对最值进行保存。
- 当新加入的值比队列末尾的值大时,则pop掉队列尾部的值,一直到可以保证新队列是递减的(可能包含相等的值)。
算法流程:
- 判断nums 的size以及k值等,增强函数的鲁棒性;
- 建立队列,用来保存最值;
- 首先根据第一个窗口的值来初始化队列;
- 之后根据窗口的移动,判断是否pop当前的队首值以及保证队列的递减性。
代码:
1 |
|
带有IO的代码:
1 |
|