题目描述
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值 。
示例
提交的代码
import java.util.Deque;
import java.util.LinkedList;
class MyQueue{
Deque<Integer> queue;
MyQueue(){
queue=new LinkedList<>();
}
void pop(int val){
if(!queue.isEmpty()&&queue.peek()==val){
queue.poll();
}
}
void push(int val){
while(!queue.isEmpty()&&queue.peekLast()<val){
queue.pollLast();
}
queue.offer(val);
}
int front(){
return queue.peek();
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
MyQueue myQueue=new MyQueue();
int[] res=new int[nums.length-k+1];
int count=0;
for(int i=0;i<k;i++){
myQueue.push(nums[i]);
}
res[count++]=myQueue.front();
for(int i=k;i<nums.length;i++){
myQueue.pop(nums[i-k]);
myQueue.push(nums[i]);
res[count++]=myQueue.front();
}
return res;
}
}
学习到的东西
上面的代码就是学到的，这个题没做出来，我写的方法时复已经到了O(n*k)了，虽然不是暴力算法，时复到了它就是暴力了。
看了大佬的方法，用的是单调队列(说实话，第一次听过)，思路就是当前的单调队列中的元素从队头到队尾是单调不递增的(后面搜了资料发现单调队列分成单调递增和单调递减两种)，所以队头的元素代表的当前滑动窗口中的最大值。
整体运行：滑动窗口移动的时候，窗口不再包含的那个元素从队列中出队(如果这个元素在队首的话，毕竟单调队列维护队首的元素就代表当前滑动窗口的最大值，如果滑动窗口要掠过它，它理应被遗弃；否则没有任何动作)，新进入窗口的元素添加至队尾，但是它会跟队列中的元素作比较（从队尾向队首方向），队列中的比它小的数字全部出队直到队列中比他大的元素为止(从队尾出队)；滑动窗口每移动一次就返回单调队列的队首元素加入int[]作为结果。
感想
我是弱智。