滑动窗口最大值(java)

题目描述

给你一个整数数组 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       31 [3  -1  -3] 5  3  6  7       31  3 [-1  -3  5] 3  6  7       51  3  -1 [-3  5  3] 6  7       51  3  -1  -3 [5  3  6] 7       61  3  -1  -3  5 [3  6  7]      7

示例 2：

输入：nums = [1], k = 1
输出：[1] 

我的代码思路：

初始化：

• 创建一个结果数组 maxwindow，长度为 nums.length - k + 1，用来存储每个滑动窗口的最大值。
• 变量 max_j：记录当前窗口中最大值的索引。
• 变量 maxnum：记录当前窗口的最大值。

滑动窗口遍历：

• 遍历从窗口的起点 i 到 nums.length−k，即所有窗口的起始位置。
• 如果之前记录的最大值索引 max_j 还在当前窗口范围内，且 max_j != 0：
  • 当前窗口的最大值可能是 maxnum 或 nums[i + k - 1]（即新加入窗口的值），因此比较两者更新 maxnum。
• 如果 max_j 不在当前窗口范围内：
  • 重新计算当前窗口的最大值 maxnum，从 i 开始遍历到窗口结束 i+k−1。
  • 在遍历过程中，记录最大值 maxnum 及其索引 max_j。

存储结果：

• 每次计算得到的最大值存储到 maxwindow[i] 中。

返回结果：

• 返回结果数组 maxwindow。

代码

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int[] maxwindow = new int[nums.length-k+1];int max_j =0; int maxnum=nums[0];for(int i = 0;i<maxwindow.length;i++){if(max_j>=i && max_j !=0){maxnum = Math.max(maxnum,nums[i+k-1]);}else{maxnum = nums[i];for(int j=i+1;j<i+k;j++){maxnum = Math.max(maxnum,nums[j]);if(nums[j]==maxnum){max_j = j;}}}maxwindow[i] =maxnum;}return maxwindow;}
}

代码的优化点

该代码在重新计算窗口最大值时，需要从头开始遍历窗口中的元素，导致最坏情况下的时间复杂度为 O(nk)，其中 n 是数组长度，k是窗口大小。

改进思路

• 使用双端队列存储数组中元素的索引，从队首到队尾保持一个单调递减的顺序。
• 队列中的索引始终对应当前滑动窗口范围内的元素。
• 队列的操作规则保证队首元素总是当前窗口的最大值。

算法步骤

1. 初始化：

   • 创建一个结果数组 maxwindow，长度为 nums.length - k + 1。
   • 使用双端队列 Deque 存储索引。

2. 滑动窗口遍历：

   • 遍历数组 nums 中的每个元素，索引为 i。
   • 移除队首的无效索引（队首索引小于 i−k+1，说明超出当前窗口范围）。
   • 从队尾开始移除所有比当前元素 nums[i] 小的索引（这些索引对应的值不可能成为当前或后续窗口的最大值）。
   • 将当前元素的索引 i 加入队尾。
   • 如果 i 达到 k−1 或更大，将队首的元素（当前窗口最大值）加入结果数组。

3. 返回结果：

   • 遍历完成后，返回结果数组 maxwindow。

代码

import java.util.Deque;
import java.util.LinkedList;
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if (nums == null || nums.length == 0) return new int[0];int n = nums.length;int[] maxwindow = new int[n - k + 1];Deque<Integer> deque = new LinkedList<>();     for (int i = 0; i < n; i++) {// 移除超出窗口范围的索引if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {deque.pollFirst();}     // 移除所有队尾比当前元素小的索引while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {deque.pollLast();} // 加入当前元素的索引deque.offerLast(i);      // 当前窗口的最大值加入结果if (i >= k - 1) {maxwindow[i - k + 1] = nums[deque.peekFirst()];}}        return maxwindow;}
}

查漏补缺：

Deque相关方法详解_deque方法-CSDN博客

【Java】Java双端队列Deque使用详解_dequeuejava-CSDN博客

【Java】Java队列Queue使用详解_java queue-CSDN博客