滑动窗口最大值

理解题目：

题目要求在给定整数数组 nums 和滑动窗口的大小 k 的情况下，找到滑动窗口中的最大值。

代码实现：

import java.util.ArrayDeque;
import java.util.Deque;

public class SlidingWindowMaximum {
    // 滑动窗口最大值
    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];
        int index = 0;
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            // 移除窗口左边界外的元素
            while (!deque.isEmpty() && deque.peek() < i - k + 1) {
                deque.poll();
            }

            // 移除队列中比当前元素小的元素，保证队首元素是当前窗口的最大值
            while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
                deque.pollLast();
            }

            deque.offer(i); // 将当前索引加入队列

            // 添加窗口最大值到结果数组
            if (i >= k - 1) {
                result[index++] = nums[deque.peek()];
            }
        }

        return result;
    }
}

步骤解释：

1. 首先检查数组是否为空，滑动窗口大小是否有效，如果无效则返回空数组。

2. 创建一个结果数组 result 用于存储每个滑动窗口的最大值，初始化结果数组的索引 index 为0。

3. 创建一个双端队列 deque，用于存储当前窗口中的元素索引。

4. 遍历整个数组 nums，对于每个元素：

• 移除双端队列中窗口左边界外的元素，即索引小于当前窗口左边界的元素。
• 移除队列中比当前元素小的元素，保证队首元素是当前窗口的最大值。
• 将当前索引加入队列。
• 如果当前索引大于等于窗口大小 k - 1，说明窗口形成完毕，将窗口最大值加入结果数组中。

5. 返回结果数组 result。

时间复杂度：遍历数组一次，时间复杂度为 O(n)。

空间复杂度：双端队列 deque 最坏情况下需要存储窗口大小的元素，空间复杂度为 O(k)。