🔗 滑动窗口最大值

题目来源：239. 滑动窗口最大值 – 力扣（LeetCode）

---

📌 题目描述

给你一个整数数组 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
  • 窗口 [3,-1,-3] → 最大值 3
  • 窗口 [-1,-3,5] → 最大值 5
  • 窗口 [-3,5,3] → 最大值 5
  • 窗口 [5,3,6] → 最大值 6
  • 窗口 [3,6,7] → 最大值 7

示例 2：

• 输入：nums = [1], k = 1
• 输出：[1]
• 解释：只有一个元素，最大值就是它本身。

示例 3：

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

---

⚠️ 提示

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴
• 1 <= k <= nums.length

---

💡 解法：单调队列（双端队列）—— O(n) 时间，O(k) 空间

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int length = nums.length;
        int[] ans = new int[length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        for (int i = 0; i < length; i++) {
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.pollLast();
            }
            deque.addLast(i);
            if (i >= k - 1) {
                ans[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        return ans;
    }
}

---

📊 复杂度分析

• 时间复杂度：O(n)
  每个元素最多入队和出队一次，整体遍历为线性时间。
• 空间复杂度：O(k)
  双端队列中最多存储 k 个索引（窗口大小），因此空间复杂度为 O(k)。
  返回数组不计入额外空间。

---

🧩 解题思路

1. 核心挑战：
   暴力解法（对每个窗口遍历 k 个元素找最大值）时间复杂度为 O(nk)，在 n 较大时会超时。
   需要一种动态维护窗口最大值的数据结构。
2. 单调队列思想：
   使用一个双端队列（Deque），存储数组索引，并维护队列中对应值的单调递减性。
   • 队首始终是当前窗口中最大值的索引。
   • 队列中只保留“可能成为未来最大值”的元素。
3. 维护单调性：
   • 步骤 1：移除过期元素
     若队首索引已不在当前窗口内（< i - k + 1），将其从队首移除。
   • 步骤 2：维护递减性
     若当前元素 nums[i] 大于队尾对应值，则不断从队尾弹出，直到队列为空或队尾值更大。
     这样可以“淘汰”掉那些比当前元素小且位置更靠前的数——它们不可能再成为最大值。
   • 步骤 3：当前索引入队
     将当前索引 i 加入队尾。
4. 获取最大值：
   当 i >= k - 1 时，说明窗口已形成，此时队首元素即为当前窗口最大值的索引，nums[deque.peekFirst()] 即为所求。
5. 举例说明：
   对于 nums = [1,3,-1], k = 3：
   • i=0: 队列为空 → 加入索引 0 → deque=[0]
   • i=1: 3 > 1 → 弹出 0，加入 1 → deque=[1]
   • i=2: -1 < 3 → 直接加入 2 → deque=[1,2]
     此时 i=2 >= 2，取队首 nums[1]=3 → 最大值为 3