LeetCode 239. 滑动窗口最大值

更多题解尽在 https://sugar.matrixlab.dev/algorithm 每日更新。
组队打卡，更多解法等你一起来参与哦！

LeetCode 239. 滑动窗口最大值，难度困难。

双端队列

解题思路：看到这题的第一眼就是优先队列，获取前第 K 个数字（回顾一下题型和解法）。剩下的就是暴力，但是暴力会超时，小伙伴们可以自行试一下（能暴力绝不动脑子）。讲一下本题思路：直接遍历数组

• 遍历每个元素时，首先检查双端队列的头部元素是否在当前滑动窗口范围内，如果不在，则移除。
• 然后移除双端队列尾部所有比当前元素小的元素，因为这些元素不会再成为滑动窗口中的最大值。
• 将当前元素的索引添加到双端队列的尾部。
• 当处理的元素数大于等于 k - 1 时，将当前滑动窗口的最大值（即双端队列头部的元素）添加到结果数组中。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        if (nums.length == 0) {
            return result;
        }
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < nums.length; ++i) {
            // 移除不在滑动窗口范围内的元素
            if (!deque.isEmpty() && deque.peekFirst() == i - k) {
                deque.pollFirst();
            }

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

            // 添加当前元素的索引
            deque.offerLast(i);

            // 当前滑动窗口的最大值添加到结果中
            if (i >= k - 1) {
                result[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return result;
    }
}