Sliding Window Maximum: tại sao monotonic deque rút gọn O(n*k) xuống còn O(n)

Cửa sổ trượt. Giá trị max thay đổi. Và mọi cách tiếp cận ngây thơ đều tốn O(k) mỗi bước — chấp nhận được khi k nhỏ, đau đớn khi k gần bằng n, thảm họa khi cả hai đều ở mức 10^5. Câu hỏi thực sự mà bài toán này đặt ra là: liệu bạn có thể duy trì running maximum qua một cửa sổ di chuyển mà không cần tính lại từ đầu mỗi lần không?

Câu trả lời là có, và cơ chế đó là monotonic deque. Trước khi đến đó, đáng dành một chút thời gian với brute force — không phải để bác bỏ nó, mà để thấy chính xác công việc nào nó đang làm một cách không cần thiết.

Đề bài

Cho một mảng số nguyên và một sliding window kích thước k di chuyển từ trái sang phải mỗi lần một vị trí; tại mỗi vị trí bạn chỉ thấy k số nằm trong cửa sổ. Trả về mảng các giá trị lớn nhất — một giá trị cho mỗi vị trí cửa sổ. Xem đề gốc: LeetCode 239.

Ràng buộc:
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4
- 1 <= k <= nums.length

Các constraint nói gì

n lên đến 10^5 và k từ 1 đến n. Có n - k + 1 cửa sổ. Nếu quét toàn bộ mỗi cửa sổ, bạn tốn O(k) mỗi cửa sổ và O(n * k) tổng cộng. Khi k = n / 2, đó là O(n^2 / 2). Với n = 10^5, con số này là năm tỷ phép tính. Không time limit nào chịu được điều đó.

Constraint 1 <= k <= n nghĩa là bạn không bao giờ có cửa sổ rỗng và không cần xử lý trường hợp cửa sổ không khớp. Dải giá trị [-10^4, 10^4] có nghĩa là số âm hoàn toàn bình thường — không được dùng 0 làm sentinel. Giá trị lớn nhất trong bất kỳ cửa sổ nào luôn là số nguyên hợp lệ.

Những constraint này cộng lại dẫn đến một kết luận duy nhất: cần O(n) về time. Kích thước cửa sổ k không được xuất hiện trong thành phần dominant của bạn. Mọi thứ khác suy ra từ đó.

Approach 1: Brute Force

Với mỗi vị trí bắt đầu của cửa sổ, quét tất cả k phần tử và ghi lại giá trị lớn nhất. Trực tiếp, rõ ràng, và quá chậm với input lớn.

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        result = []
        for i in range(n - k + 1):
            window_max = nums[i]
            for j in range(i, i + k):
                window_max = max(window_max, nums[j])
            result.append(window_max)
        return result

public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k) {
        int n = nums.Length;
        int[] result = new int[n - k + 1];
        for (int i = 0; i <= n - k; i++) {
            int windowMax = nums[i];
            for (int j = i; j < i + k; j++) {
                windowMax = Math.Max(windowMax, nums[j]);
            }
            result[i] = windowMax;
        }
        return result;
    }
}

Time: O(n * k) — vòng ngoài chạy n - k + 1 lần, vòng trong chạy k lần mỗi iteration. Space: O(1) auxiliary — không tính mảng kết quả theo convention.

Brute force có một điểm kém hiệu quả cụ thể: khi cửa sổ trượt một vị trí sang phải, bạn tính lại max trên k - 1 phần tử đã có trong cửa sổ trước. Bạn đang bỏ đi thông tin. Approach deque giữ đúng thông tin bạn cần.

Approach 2: Monotonic Deque

Ý tưởng là duy trì một deque (double-ended queue) chứa các index có giá trị tương ứng theo thứ tự giảm dần. Đầu deque luôn chứa index của phần tử lớn nhất trong cửa sổ hiện tại. Khi cửa sổ trượt, bạn thực hiện:

1. Loại bỏ phần tử đầu nếu nó đã ra ngoài cửa sổ.
2. Trước khi đẩy index mới, pop từ cuối deque bất kỳ index nào có giá trị <= phần tử mới — các phần tử đó giờ vô dụng, vì phần tử mới vừa lớn hơn vừa ở trong cửa sổ lâu hơn.
3. Đẩy index hiện tại vào cuối.
4. Đọc giá trị lớn nhất từ đầu deque.

Tại sao dùng <= thay vì < khi pop? Vì nếu hai phần tử bằng nhau tồn tại và phần tử trước sắp rời cửa sổ, giữ nó lại tạo ra một "max ảo". Pop theo <= giữ deque sạch và đầu deque luôn hợp lệ.

from collections import deque
 
class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        dq: deque[int] = deque()  # lưu index, không lưu giá trị
        result = []
 
        for i in range(len(nums)):
            # 1. loại bỏ đầu nếu nằm ngoài cửa sổ hiện tại
            while dq and dq[0] < i - k + 1:
                dq.popleft()
 
            # 2. pop từ cuối bất kỳ index nào có giá trị <= nums[i]
            while dq and nums[dq[-1]] <= nums[i]:
                dq.pop()
 
            # 3. đẩy index hiện tại
            dq.append(i)
 
            # 4. cửa sổ đầy khi i >= k - 1
            if i >= k - 1:
                result.append(nums[dq[0]])
 
        return result

using System;
using System.Collections.Generic;
 
public class Solution {
    public int[] MaxSlidingWindow(int[] nums, int k) {
        var dq = new LinkedList<int>();  // lưu index
        var result = new List<int>();
 
        for (int i = 0; i < nums.Length; i++) {
            // 1. loại bỏ đầu nếu nằm ngoài cửa sổ
            while (dq.Count > 0 && dq.First.Value < i - k + 1) {
                dq.RemoveFirst();
            }
 
            // 2. pop cuối khi giá trị <= nums[i]
            while (dq.Count > 0 && nums[dq.Last.Value] <= nums[i]) {
                dq.RemoveLast();
            }
 
            // 3. đẩy index hiện tại
            dq.AddLast(i);
 
            // 4. ghi kết quả khi cửa sổ đầu tiên đã đủ
            if (i >= k - 1) {
                result.Add(nums[dq.First.Value]);
            }
        }
 
        return result.ToArray();
    }
}

Time: O(n) — mỗi index vào deque đúng một lần và ra tối đa một lần. Các vòng while bên trong có độ phức tạp amortized O(1) mỗi vòng ngoài. Space: O(k) — deque chứa tối đa k index tại bất kỳ thời điểm nào.

Trace tay: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

Từng bước:

• i=0: deque rỗng, đẩy 0. dq=[0]. Chưa đến k-1=2.
• i=1: nums[1]=3 > nums[0]=1, pop 0. Đẩy 1. dq=[1]. Chưa sẵn sàng.
• i=2: nums[2]=-1 < nums[1]=3, không pop. Đẩy 2. dq=[1,2]. i >= 2 -> kết quả nhận nums[1]=3.
• i=3: đầu=1, 1 >= 3-3+1=1, vẫn trong cửa sổ. nums[3]=-3 < nums[2]=-1, không pop. Đẩy 3. dq=[1,2,3]. Kết quả nhận nums[1]=3.
• i=4: đầu=1, 1 < 4-3+1=2, loại bỏ. dq=[2,3]. Giờ nums[4]=5 > nums[3]=-3, pop 3. nums[4]=5 > nums[2]=-1, pop 2. Đẩy 4. dq=[4]. Kết quả nhận nums[4]=5.
• i=5: đầu=4, trong cửa sổ. nums[5]=3 < nums[4]=5, không pop. Đẩy 5. dq=[4,5]. Kết quả nhận nums[4]=5.
• i=6: đầu=4, 4 < 6-3+1=4 sai (4 không < 4), giữ đầu. nums[6]=6 > nums[5]=3, pop 5. nums[6]=6 > nums[4]=5, pop 4. Đẩy 6. dq=[6]. Kết quả nhận nums[6]=6.
• i=7: đầu=6, 6 < 7-3+1=5 sai. nums[7]=7 > nums[6]=6, pop 6. Đẩy 7. dq=[7]. Kết quả nhận nums[7]=7.

Kết quả cuối: [3, 3, 5, 5, 6, 7]. Khớp với output mong đợi.

Invariant xuyên suốt: deque luôn giảm đơn điệu theo giá trị từ đầu đến cuối, và mọi index trong deque đều nằm trong cửa sổ hiện tại.

Các edge case cần phân tích kỹ

k = 1: Mỗi phần tử là cửa sổ của chính nó. Deque luôn chứa đúng một phần tử tại một thời điểm. Ở mỗi bước, vòng pop-cuối làm rỗng deque ngay vì phần tử cũ <= phần tử hiện tại, hoặc bước loại bỏ đầu xóa nó. Kết quả chỉ là bản sao của nums. Cả hai approach xử lý đúng mà không cần xử lý đặc biệt.

k = n: Đúng một cửa sổ chứa tất cả phần tử. Deque tích lũy index qua toàn bộ mảng trong giai đoạn warmup và trả về một kết quả duy nhất tại i = n - 1. Brute force trả về [max(nums)] một cách hiển nhiên.

Tất cả phần tử bằng nhau (ví dụ [5, 5, 5, 5]): Pop-cuối dùng <=, nên các phần tử bằng nhau bị pop. Deque luôn chứa đúng một index — index gần đây nhất. Loại bỏ đầu sau đó xóa nó đúng lịch. Kết quả là mảng hằng số với giá trị lặp lại. Nếu dùng < thay vì <= trong điều kiện pop, deque có thể chứa các giá trị bằng nhau cũ; vẫn cho kết quả đúng nhưng <= sạch hơn.

Mảng giảm đơn điệu (ví dụ [9, 7, 5, 3], k = 2): Deque không bao giờ pop từ cuối — mỗi phần tử mới đều nhỏ hơn. Deque tăng lên kích thước 2, rồi loại bỏ đầu giữ nó ở kích thước 1 khi cửa sổ trượt. Bạn luôn đọc phần tử ngoài cùng bên trái trong cửa sổ là maximum.

Mảng tăng đơn điệu (ví dụ [1, 3, 5, 7], k = 2): Mỗi phần tử mới lớn hơn tất cả phần tử trước. Pop-cuối làm rỗng deque hoàn toàn ở mỗi bước. Deque luôn có đúng một index — vị trí hiện tại — và kết quả là nums[1:], đúng.

Một phần tử n = 1, k = 1: Một cửa sổ, một phần tử. Vòng lặp chạy một lần, deque nhận [0], i >= k-1=0 đúng, kết quả là [nums[0]].

Deque là bộ lọc "ứng viên hữu ích"

Mental model tôi hay dùng: deque lưu các index của những ứng viên vẫn có thể là maximum của cửa sổ trong tương lai. Một index là ứng viên chỉ khi:

1. Nó nằm trong cửa sổ hiện tại (loại bỏ đầu xử lý điều này).
2. Không có index mới hơn trong cửa sổ với giá trị lớn hơn (pop-cuối xử lý điều này).

Bất kỳ index nào vi phạm điều kiện 2 có thể bị bỏ mãi mãi — nếu phần tử j trong cửa sổ với nums[j] <= nums[i] và j < i, thì trong khi phần tử j còn trong cửa sổ, phần tử i cũng ở trong cửa sổ và ít nhất bằng nhau. Và sau khi phần tử j rời đi, phần tử i vẫn còn đó. Vậy j không đóng góp gì.

Đây là lý do deque kết thúc được sắp xếp giảm dần: mỗi lần đẩy index mới, bạn đã xóa hết mọi thứ nhỏ hơn. Đầu deque luôn là ứng viên lớn nhất còn lại.

Bảng so sánh

Không có ngưỡng nào mà tôi sẽ ship brute force. Dù k nhỏ, code deque chỉ phức tạp hơn một chút và scale tốt với bất kỳ input nào. Trong phỏng vấn, tôi sẽ viết thẳng giải pháp deque sau khi biết constraint — ràng buộc n = 10^5 đã kết thúc cuộc tranh luận.

Vị trí trong series sliding window

Các bài trước trong series này — Best Time to Buy and Sell Stock, Longest Repeating Character Replacement, Minimum Window Substring — đều dùng two-pointer hoặc shrinkable window. Bài này giới thiệu một primitive khác: monotonic deque. Thay vì điều chỉnh ranh giới cửa sổ dựa trên điều kiện hợp lệ, bạn duy trì một cấu trúc phụ theo dõi maximum qua cửa sổ kích thước cố định.

Pattern nền có thể chuyển giao: bất cứ khi nào cần running extremum (max hoặc min) qua fixed-size sliding window, monotonic deque cho bạn O(n). Min-deque chỉ đổi điều kiện pop từ <= thành >=.

Bốn bài liên quan phát triển cùng ý tưởng:

Sliding Window Median (480) — thay vì max, theo dõi median. Một deque duy nhất không đủ; cần hai heap (max-heap cho nửa dưới, min-heap cho nửa trên) và bước rebalance khi cửa sổ trượt. Khó implement hơn nhiều, cùng frame sliding window.

Shortest Subarray with Sum at Least K (862) — kết hợp monotonic deque với prefix sum. Deque theo dõi prefix sum tăng đơn điệu, và bạn tìm vị trí gần nhất trước đó làm cho tổng subarray đủ lớn. Cửa sổ ở đây không có kích thước cố định, đó là điều làm nó khó.

Jump Game VI (1696) — bài DP trong đó transition là dp[i] = nums[i] + max(dp[i-k..i-1]). Deque duy trì maximum của k giá trị dp trước, biến O(n * k) DP thành O(n). Cấu trúc deque giống hệt những gì bạn đã xây dựng ở đây.

Constrained Subsequence Sum (1425) — cùng ý tưởng với Jump Game VI: một bài DP trong đó mỗi state phụ thuộc vào maximum của k state trước. Tối ưu hóa bằng deque áp dụng trực tiếp.

Khi bạn đã có pattern monotonic deque trong đầu, bốn bài này trở thành các biến thể có thể nhận ra thay vì các bài toán mới hoàn toàn.