AcWing 79. 滑动窗口的最大值--Java代码
原题链接
困难
作者:
木木灬
,
2019-05-07 15:56:11
,
所有人可见
,
阅读 1388
算法1
(队列) $O(n)$
- 先判断队列是否为空,如果为空,将当前的下标放进队列作为最大值;
- start用来检测当前队列中的最大值是否已经离开滑动窗口,所以一开始start=i-k+1,如果start大于队列中最大值的下标,则弹出最大值
- 然后判断队列是否为空,并且从队列尾与当前值比较,来更新队列中的最大值;
- 当start。=0时,说明滑动窗口已经完全进入数组,可以开始记录最大值了
Java 代码
class Solution {
public int[] maxInWindows(int[] nums, int k) {
int[] res = new int[nums.length-k+1];
if(k==0)return res;
int start;
int index = 0;
ArrayDeque<Integer> max = new ArrayDeque<>();
for(int i=0;i<nums.length;i++){
start = i-k+1;
if(max.isEmpty())
max.add(i);
else if(start>max.peekFirst())
max.pollFirst();
while((!max.isEmpty())&&nums[max.peekLast()]<=nums[i])
max.pollLast();
max.add(i);
if(start>=0)
res[index++] = nums[max.peekFirst()];
}
return res;
}
}
好