1、题目
image.png
2、分析
使用单调队列的方法
https://labuladong.github.io/zgnb/6/34/
3、代码
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
MonotoneQueue window = new MonotoneQueue();
List<Integer> res = new ArrayList<>();
for(int i = 0; i < nums.length; i++){
if(i < k - 1){
window.push(nums[i]);
}else{
window.push(nums[i]);
res.add(window.max());
window.pop(nums[i - k + 1]);
}
}
int[] ans = new int[res.size()];
for(int i = 0; i < res.size(); i++){
ans[i] = res.get(i);
}
return ans;
}
}
class MonotoneQueue{
LinkedList<Integer> queue = new LinkedList<>();
public void push(int x){
while(!queue.isEmpty() && queue.getLast() < x){
queue.removeLast();
}
queue.addLast(x);
}
public void pop(int x){
if(queue.getFirst() == x){
queue.removeFirst();
}
}
public int max(){
return queue.getFirst();
}
}
