LeetCode_239_滑动窗口最大值
给定一个数组 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 <= nums.length <= 10^5-10^4 <= nums[i] <= 10^41 <= k <= nums.length维护一个双端队列, 队列中存储滑动窗口的值的数组索引(降序), 然后获取队头元素即为滑动窗口最大值; 注意需要维护双端队列, 删除小于nums[i]的队尾元素, 删除不存在与滑动窗口中的元素; 在遍历滑动窗口时, 双端队列中至少会存在一个值, 且该值为滑动窗口中的最大值;
public int[] maxSlidingWindow(int[] nums, int k) { if(nums == null || nums.length == 0 || k <= 1) return nums; Deque<Integer> deque = new LinkedList<>(); //维护一个双端队列, 用于存储当前滑动窗口中的降序排列 int[] maxes = new int[nums.length - k + 1]; int wIndex = -k+1; //滑动窗口的起始索引位置 for (int i = 0; i < nums.length; i++,wIndex++) { /** * 维护双端队列中的升序排列 */ //如果队列尾部元素小于等于nums[i] while(!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]){ deque.pollLast(); } //如果队列尾部元素大于等于nums[i] deque.offerLast(i); /** * 检查队头元素是否合法(可能对头元素已不存在当前滑动窗口中), 每一轮循环只会导致一个队头元素失效 */ if(deque.peekFirst() < wIndex){ deque.pollFirst(); } /** * 获取当前窗口的最大值 */ if(wIndex >= 0){ maxes[wIndex] = nums[deque.peekFirst()]; } } return maxes; }
使用一个变量维护每个窗口的最大值索引, 并且1. 在索引失效后重新遍历窗口内的元素计算最大值索引, 2. 判断右侧新加入的元素是否可以更新最大值索引
public int[] maxSlidingWindow_(int[] nums, int k) { if(nums == null || nums.length == 0 || k <= 1) return nums; int[] maxes = new int[nums.length - k + 1]; //初始化前k个元素的最大值 int maxIdx = 0; for (int i = 1; i < k; i++) { //为什么使用>=? 因为需要尽可能的让maxId的值为较新的值, 避免maxIdx失效后需要重新遍历k个元素,寻找最大值 if(nums[i] >= nums[maxIdx]) maxIdx = i; } for (int leftIdx = 0; leftIdx < maxes.length; leftIdx++) { int rightIdx = leftIdx + k - 1; //根据滑窗左侧索引位置计算右侧位置索引 /** * 如果窗口最右侧进入窗口内的值大于最大索引的值, 那么更新索引 * * 为什么要把最大值判断放前面 ? * 因为, 如果新进来的值刚好大于已经失效的最大索引, 那么可以直接更新最大索引, 避免再进入一次窗口遍历 */ if(nums[rightIdx] >= nums[maxIdx]){ maxIdx = rightIdx; }else{ /** * 如果最大索引失效且最新进来的元素并不能更新为最大索引,则需要重新遍历窗口元素获取当前最大索引 */ if(maxIdx < leftIdx){ maxIdx = leftIdx; for(int j = leftIdx + 1; j <= rightIdx; j++){ if(nums[j] >= nums[maxIdx]) maxIdx = j; } } } //此时已计算出当前窗口的最大值 maxes[leftIdx] = nums[maxIdx]; } return maxes; }
