LeetCode220831_92、滑动窗口最大值
给你一个整数数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1:
输入: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
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/sliding-window-maximum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解、用队列双端存储数组的索引,根据索引对应元素判断是否需要弹出队尾和队首。
当 (索引+ 1)未达到窗口长度时,不记录最大值,并且当后续元素大于队尾元素时弹出队尾元素,保障队首为最大
队首元素是否在窗口长度内,若queue.peek() <= i - k 则说明队首元素已在窗口外,需要弹出。
满足窗口长度后,每进行一次遍历在结果数组添加有效的队首元素。
class Solution{
public int[] maxSlidingWindow(int[] nums, int k){
if(nums == null || nums.length < 2) return nums;
LinkedList<Integer> queue = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
for(int i = 0; i < nums.length; i++){
while(!queue.isEmpty() && nums[i] > nums[queue.peekLast()]){
queue.pollLast();
}
queue.addLast(i);
if(queue.peek() <= i - k){
queue.poll();
}
if(i + 1 >= k){
res[i + 1 - k] = nums[queue.peek()];
}
}
return res;
}
}