byte-by-byte — 2026-04-11

← 2026-04-10 📂 All Days 2026-04-12 →

🔬 Saturday Deep Dive: Sliding Window Maximum (15 min read)

📊 NeetCode: 19/150 · SysDesign: 18/40 · Behavioral: 18/40 · Frontend: 18/50 · AI: 8/30

🔥 21-day streak!

🔗 LeetCode 239: Sliding Window Maximum

📹 NeetCode Video

Overview / 概述

滑动窗口最大值 是一个经典的困难级别算法问题。给定一个数组 nums 和一个大小为 k 的滑动窗口，窗口从数组的最左侧移动到最右侧，每次只向右移动一位。你需要返回每次窗口中的最大值。

这个问题之所以重要，是因为它完美地展示了如何使用单调队列 (Monotonic Queue) 将一个 $O(N \times K)$ 的暴力解法优化到 $O(N)$ 的时间复杂度。

Sliding Window Maximum is a classic Hard-level algorithm problem. Given an array nums and a sliding window of size k moving from the far left to the far right, you need to return the maximum value in the window at each step.

This problem is crucial because it perfectly demonstrates how to use a Monotonic Queue to optimize an $O(N \times K)$ brute-force solution down to $O(N)$ time complexity.

Part 1: Theory / 理论基础 (5 min)

单调队列 (Monotonic Queue)

核心思想是维护一个双端队列（Deque），队列中存储的是数组元素的索引，并且这些索引对应的元素在队列中是严格递减的。

为什么存索引？因为我们需要判断队首的元素是否已经滑出了当前的窗口。
为什么递减？因为如果新来的元素比队尾的元素大，那么队尾的元素永远不可能成为当前或未来窗口的最大值（它更小，而且更早离开窗口）。所以我们可以安全地将其弹出。

Monotonic Queue

The core idea is to maintain a double-ended queue (Deque) that stores the indices of the array elements, and the elements corresponding to these indices are strictly decreasing in the queue.

Why store indices? Because we need to check if the element at the front of the queue has slid out of the current window.
Why decreasing? Because if a newly arrived element is larger than the element at the back of the queue, the back element can never be the maximum of the current or any future window (it's smaller and will leave the window earlier). Thus, we can safely pop it.

Part 2: Step-by-Step Implementation / 一步一步实现 (8 min)

Naive Approach ($O(N \times K)$)

遍历每个窗口，然后在窗口内遍历找到最大值。

Iterate through each window, and then iterate within the window to find the maximum.

def maxSlidingWindow_naive(nums, k):
    if not nums: return []
    res = []
    for i in range(len(nums) - k + 1):
        res.append(max(nums[i:i+k]))
    return res

Optimal Approach: Monotonic Deque ($O(N)$)

import collections

def maxSlidingWindow(nums, k):
    # Deque will store indices, and the values at these indices will be in decreasing order.
    # q[0] will always be the index of the maximum element in the current window.
    q = collections.deque()
    res = []
    
    for i, n in enumerate(nums):
        # 1. Remove indices that are out of the current window
        # The window is from i - k + 1 to i. So if q[0] < i - k + 1, it's out.
        if q and q[0] < i - k + 1:
            q.popleft()
            
        # 2. Remove smaller elements from the back of the queue
        # Since the current element 'n' is larger, the smaller elements 
        # before it can never be the maximum in this or future windows.
        while q and nums[q[-1]] < n:
            q.pop()
            
        # 3. Add the current element's index to the queue
        q.append(i)
        
        # 4. If our window has reached size k, add the max to the result
        # The first window is formed when i reaches k - 1
        if i >= k - 1:
            res.append(nums[q[0]])
            
    return res

Part 3: Edge Cases & Gotchas / 边界情况 (2 min)

$K = 1$: 窗口大小为1，直接返回原数组即可。 (Window size 1, return the original array).
数组为空: 返回空数组。 (Empty array: return empty array).
队列中存储值而不是索引: 如果存值，就无法判断该值是否已经滑出窗口。必须存索引！(Storing values instead of indices in the deque: If you store values, you can't tell if the max value has slid out of the window. You MUST store indices!)

Part 4: Real-World Application / 实际应用 (2 min)

实时数据流分析 (Real-time Data Stream Analysis): 计算过去 $K$ 分钟内的最高股票价格、最大网络流量峰值。 (Calculating the highest stock price or peak network traffic in the last $K$ minutes).
系统监控 (System Monitoring): 监控滑动时间窗口内的最大 CPU 利用率，以触发警报。 (Monitoring max CPU utilization over a sliding time window to trigger alerts).

Part 5: Interview Simulation / 面试模拟 (3 min)

Q: 为什么时间复杂度是 $O(N)$ 而不是 $O(N \times K)$？

A: 每个元素的索引最多被推入队列一次，弹出队列一次。所以 while 循环在整个执行过程中最多运行 $N$ 次，摊还时间复杂度为 $O(1)$，总时间 $O(N)$。

(Why is the time complexity $O(N)$? Each index is pushed and popped at most once. The while loop runs at most $N$ times globally, making it amortized $O(1)$ per element.)

Q: 空间复杂度是多少？

A: $O(K)$，因为双端队列中最多只会存储 $K$ 个元素的索引。

(What is the space complexity? $O(K)$, because the deque will store at most $K$ indices at any time.)

Q: 如果要求窗口内的最小值呢？

A: 只需要将单调队列的维护规则反转，保持队列内的元素严格递增即可。

(What if we need the minimum in the window? Just reverse the monotonic property: maintain a strictly increasing queue.)

Q: 可以用最大堆 (Max Heap) 解决吗？

A: 可以，将 (-value, index) 放入堆中。每次取堆顶，如果堆顶元素的索引不在窗口内就弹出。时间复杂度是 $O(N \log N)$，不如单调队列优。

(Can we use a Max Heap? Yes, store (-value, index). Pop the top if its index is out of bounds. But time complexity is $O(N \log N)$, which is suboptimal.)

Q: 这个模式还能解决什么问题？

A: 任何需要在滑动窗口中寻找极值的问题，比如 LeetCode 862 (和至少为 K 的最短子数组) 也用到了单调队列的思想。

(What else can this pattern solve? Any problem requiring extrema in a sliding window, like LC 862: Shortest Subarray with Sum at Least K.)

Saturday, April 11, 2026