每日一题-滑动窗口最大值

常规话题 快问快答
1

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

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

示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

示例 2：

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

请使用JAVA实现该算法

1 个赞
2 
import java.util.ArrayDeque;
import java.util.Deque;

public class A {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k == 0) return new int[0];
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++) {
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }
            deque.offer(i);
            if (i - deque.peek() >= k) {
                deque.poll();
            }
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peek()];
            }
        }
        return result;
    }
}
3

巨佬，这道题的核心思路是什么

4

主要是 维护一个双端队列 然后让队列中始终保持着当前滑动窗口内的最大值的索引

3 个赞
5

这种题GPT会做吗？

GPT写的 
import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }
        int n = nums.length;
        int[] result = new int[n - k + 1]; // 结果数组
        Deque<Integer> deque = new LinkedList<>(); // 双端队列，存储元素索引

        for (int i = 0; i < n; i++) {
            // 移除不在滑动窗口内的元素的索引
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }

            // 移除所有比当前元素小的元素的索引
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            // 将当前元素索引添加到双端队列
            deque.offer(i);

            // 当达到窗口大小时，记录当前窗口的最大值
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peek()];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1,3,-1,-3,5,3,6,7};
        int k = 3;
        int[] result = solution.maxSlidingWindow(nums, k);
        for (int num : result) {
            System.out.print(num + " ");
        }
    }
}
6

肯定会 这种很简单的 基本最优解都是这么个大概写法

7

谢谢！

8

瞄了一眼 gpt写的 和我的基本一样 就多了注释

9

对对对，我也把你写的问他了，他说很漂亮 :grin: :grin:

10

之前找工作时候写的，现在回看，发现自己之前好强，现在全还回去了

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 单调递减双端队列 队列中维护数组下标
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        List<Integer> res = new ArrayList<>();
        for(int i = 0;i<nums.length;i++) {
            while(!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                // 窗口是右移的，nums[i]比队列中的大而且存活更久，也就是说队列中的无法成为最大值
                deque.pollLast();
            }
            deque.offerLast(i);
            if(i+1>=k) {
                // 开始从队头取答案，需要保证队头在当前合法区间内[i-k+1,i]
                while(!deque.isEmpty() && deque.peekFirst() < i-k+1) {
                    deque.pollFirst();
                }
                res.add(nums[deque.peekFirst()]);
            }
        }
        int[] ans = new int[res.size()];
        int n = 0;
        for(Integer num:res) {
            ans[n] = num;
            n++;
        }
        return ans;
    }
}

半年多没登陆我的leetcode了

3 个赞
11

都有工作了还刷什么力扣 :crazy_face:

12

其实还是得刷，时刻准备着，只是太忙时候没空刷。不忙时候又太懒，只想刷论坛 :joy: :joy: :joy:

13

论坛好啊 刷啥力扣

1 个赞