双端队列实现 给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
思路 : 1 开一个双端队列 和一个结果数组(存储结果最大值的) 2 只需要把双端队列第一个设置为最大值 3 每一次满足窗口大小就 返回第一个Nums[ 队列里面的第一个值] 4 刚开始的话是要满足 队列里面填充k 个 5 满了之后,随着窗口易懂,移除第一个,那么吧nums[新的最大值下标]给res
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res=new int[nums.length-k+1];
Deque<Integer> stack=new LinkedList<>();
for(int i=0;i<nums.length;i++){ //按从大到小来 ,
while(!stack.isEmpty()&&nums[stack.peekLast()]<nums[i]){
stack.removeLast(); //当前元素小于新进的 ,那么移除原来的
}
stack.addLast(i); //添加新进的
if(stack.peekFirst()==i-k){ //如果超过了k 移除第一个元素
stack.removeFirst();
}
if(i>=k-1){ // 将最大值付给 res
res[i-k+1]=nums[stack.peekFirst()]; //从0开始 所以是i-k+1
}
}
return res;
}
}