题目链接
思路
单调队列的使用方法,可以参考【单调队列】LeetCode 面试题59 - II. 队列的最大值
在本题中将滑动窗口的移动看作往队列中放数和取数的过程,实际上和上面链接中的解法一样。
代码
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] result = new int[nums.length - k + 1];
Deque<Integer> deque = new ArrayDeque<>();
int i = 0;
int j = 0;
for(; j < k - 1; j++){
this.offer(deque, nums[j]);
}
int pos = 0;
while(j < nums.length){
int temp = nums[i];
this.offer(deque, nums[j]);
result[pos++] = deque.peekFirst();
i++;
j++;
this.poll(deque, temp);
}
return result;
}
private void offer(Deque<Integer> deque, int value){
while(!deque.isEmpty() && deque.peekLast() < value){
deque.pollLast();
}
deque.offerLast(value);
}
private void poll(Deque<Integer> deque, int value){
if(deque.peekFirst() == value){
deque.pollFirst();
}
}
}
标签:deque,nums,int,最大值,++,value,队列,239,LeetCode
From: https://www.cnblogs.com/shixuanliu/p/17266100.html