【LeetCode】239. 滑动窗口最大值

2026/9/20 19:27:45 拓冰建站浏览量

今日学习的文章链接和视频链接

leetcode题目地址：239. 滑动窗口最大值

代码随想录题解地址：代码随想录

题目简介

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

看到题目的第一想法(可以贴代码）

1. 双层for循环，每次取三个数，取其最大值，加入结果集。 //超出时间限制

//超出时间限制
public int[] maxSlidingWindow(int[] nums, int k) {ArrayList<Integer> res = new ArrayList<>();int max = -100;for (int i = 0; i < nums.length - k + 1; i++){for (int j = i; j < i + k; j++){max = Math.max(max, nums[j]);}res.add(max);max = -100000;}return res.stream().mapToInt(Integer::intValue).toArray();
}

// self - ACC
public int[] maxSlidingWindow(int[] nums, int k) {ArrayList<Integer> res = new ArrayList<>();int maxIndex = findMax(nums, k, 0);res.add(nums[maxIndex]);for(int i = k; i < nums.length; i++){if (nums[i] < nums[maxIndex] && maxIndex >= i - k + 1){}else if (nums[i] > nums[maxIndex] && maxIndex >= i - k + 1){maxIndex = i;}else if (maxIndex < i - k + 1){maxIndex = findMax(nums, k, i - k + 1);}res.add(nums[maxIndex]);}return res.stream().mapToInt(Integer::intValue).toArray();
}
public int findMax(int[] nums, int k, int left){int max = -100000;int index = 0;for (int i = left; i < left + k; i++){max = Math.max(nums[i],max);if (max == nums[i]) index = i;}return index;
}

实现过程中遇到哪些困难

1. 超出时间限制（进行一些剪枝）。

看完代码随想录之后的想法

【解题思路】单调队列，直接去除掉不需要的元素。

【想法】

1. 好厉害，思维逻辑很简便。

看完视频自己写的ACC：

// 超出了时间限制，可能某些数据结构用的有问题（类型转换耗时过久）
// 或者排序耗时太长了？
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {//遍历的队列，采用Deque数据结构Deque<Integer> d = new LinkedList<>();//存放结果ArrayList<Integer> res = new ArrayList<>();//开始遍历for(int i = 0; i < nums.length; i++){//这步是为了维持窗口大小=kif (d.size() < k){newPush(d, nums[i]);}else {//当最大的数即将移除滑动窗口时，需要重新对窗口里的数进行排序，求最大值newPop(d, nums[i], k);}if (i >= k - 1) res.add(d.getFirst());}return res.stream().mapToInt(Integer::intValue).toArray();}public void newPush(Deque<Integer> d, int inNum){//当新进来的数据>当前最大的数（首部的数），移除前面所有的元素while (d.peekFirst() != null && inNum > d.peekFirst()){d.removeFirst();}//否则直接加在末尾。d.addLast(inNum);//System.out.println("11111push: "+d.peekFirst());}public void newPop(Deque<Integer> d, int inNum, int k){//当新进来的数据>当前最大的数（首部的数），移除前面所有的元素if (inNum > d.getFirst()) {d.clear();d.addFirst(inNum);}else {//当新进来的数据<当前最大的数（首部的数），需要对当前滑动窗口求最大值d.removeFirst();d.addLast(inNum);//System.out.println("ccc: "+d.peekFirst());getMax(d, k);}//System.out.println("22222pop: "+d.peekFirst());}public Deque<Integer> getMax(Deque<Integer> d, int k){int[] arr = new int[k];Deque<Integer> temp = new LinkedList<>();temp.addAll(d);for (int i = 0; i < k; i++){arr[i] = temp.pollFirst();}int maxNum = Arrays.stream(arr).max().getAsInt();//将最大值之前的数全部清空for (int i = 0; i < k; i++){if (d.peekFirst() != maxNum){d.pollFirst();}}return d;}
}

自己的答案2.0

// 超出了时间限制，可能某些数据结构用的有问题（类型转换耗时过久）
// 或者排序耗时太长了？
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {//遍历的队列，采用Deque数据结构Deque<Integer> d = new LinkedList<>();//存放结果ArrayList<Integer> res = new ArrayList<>();//开始遍历for(int i = 0; i < nums.length; i++){//这步是为了维持窗口大小=kif (d.size() < k){newPush(d, nums[i]);}else {//当最大的数即将移除滑动窗口时，需要重新对窗口里的数进行排序，求最大值newPop(d, nums[i], k);}if (i >= k - 1) res.add(d.getFirst());//System.out.println("11111push: "+d.getFirst());}return res.stream().mapToInt(Integer::intValue).toArray();}public void newPush(Deque<Integer> d, int inNum){//当新进来的数据>当前最大的数（首部的数），移除前面所有的元素while (d.peekFirst() != null && inNum > d.peekFirst()){d.removeFirst();}//否则直接加在末尾。d.addLast(inNum);//System.out.println("11111push: "+d.peekFirst());}public void newPop(Deque<Integer> d, int inNum, int k){//当新进来的数据>当前最大的数（首部的数），移除前面所有的元素if(inNum > d.peekFirst()){d.clear();//否则直接加在末尾。d.addLast(inNum);}else{//当新进来的数据<当前最大的数（首部的数），需要对当前滑动窗口求最大值d.removeFirst();while (d.peekFirst() != null && inNum > d.peekFirst()){d.removeFirst();}d.addLast(inNum);//System.out.println("ccc: "+d.peekFirst());getMax(d, k);}//System.out.println("22222pop: "+d.peekFirst());}public Deque<Integer> getMax(Deque<Integer> d, int k){int size = d.size();int[] arr = new int[size];Deque<Integer> temp = new LinkedList<>();temp.addAll(d);for (int i = 0; i < size; i++){//弹出temp双端队列的每一个元素赋值给目标数组。arr[i] = temp.pollFirst();}int maxNum = Arrays.stream(arr).max().getAsInt();//将最大值之前的数全部清空for (int i = 0; i < k; i++){if (d.peekFirst() != maxNum){d.pollFirst();}}return d;}
}

标准答案

//解法一
//自定义数组
//它是通过和最后一个数进行比较。。不是和开头的数比较。
class MyQueue {Deque<Integer> deque = new LinkedList<>();//弹出元素时，比较当前要弹出的数值是否等于队列出口的数值，如果相等则弹出//同时判断队列当前是否为空void poll(int val) {if (!deque.isEmpty() && val == deque.peek()) {deque.poll();}}//添加元素时，如果要添加的元素大于入口处的元素，就将入口元素弹出//保证队列元素单调递减//比如此时队列元素3,1，2将要入队，比1大，所以1弹出，此时队列：3,2void add(int val) {while (!deque.isEmpty() && val > deque.getLast()) {deque.removeLast();}deque.add(val);}//队列队顶元素始终为最大值int peek() {return deque.peek();}
}class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if (nums.length == 1) {return nums;}int len = nums.length - k + 1;//存放结果元素的数组int[] res = new int[len];int num = 0;//自定义队列MyQueue myQueue = new MyQueue();//先将前k的元素放入队列for (int i = 0; i < k; i++) {myQueue.add(nums[i]);}res[num++] = myQueue.peek();for (int i = k; i < nums.length; i++) {//滑动窗口移除最前面的元素，移除是判断该元素是否放入队列myQueue.poll(nums[i - k]);//滑动窗口加入最后面的元素myQueue.add(nums[i]);//记录对应的最大值res[num++] = myQueue.peek();}return res;}
}

学习时长

略

今日收获

1. Math.max(a, b)：选出较大者

2. 获取int[]的最大值

int[] arr = new int[];

int maxNum = Arrays.stream(arr).max().getAsInt();

3. ASCII码

0~9（48~57）

A~Z（65~90）

a~z（97~122）

建站实战干货