Chương 18 - Monotonic Queue + Stack

Monotonic stack/deque = stack/deque mà các phần tử giữ đơn điệu (tăng hoặc giảm) khi đi qua. Đây là “vũ khí” mạnh nhất để giải các bài “next greater/smaller”, “range max/min in sliding window”, “largest rectangle”. Bài 8.5 (Daily Temperatures) đã teaser một chút - chương này đi sâu.

Mục tiêu chương

Sau chương này, bạn sẽ:

  • Stack tăng dần → next/previous smaller; giảm dần → next/previous greater.
  • Monotonic deque cho sliding window max/min.
  • Pattern “contribution của mỗi phần tử” (sum of subarray min/max).
  • Mỗi index push/pop tối đa 1 lần → tổng O(n) amortized.

Khi nào dùng pattern này?

  • Bài “next greater / smaller” element.
  • Bài “largest rectangle / area under curve”.
  • Bài cần min/max trong sliding window.
  • Bài đếm subarray theo điều kiện monotonic.

Khi nào tăng, khi nào giảm? - Stack tăng dần (top là max của stack): hữu ích cho “previous smaller”. - Stack giảm dần (top là min): cho “previous greater” / “next greater”.

Invariant của Monotonic Stack/Deque

Sự khác biệt giữa “stack thường” và “monotonic stack” là invariant - quy luật luôn đúng tại mọi thời điểm. Hiểu invariant = hiểu cả pattern.

Monotonic decreasing stack (giảm dần từ đáy → đỉnh) 

Invariant tại mọi thời điểm:
   bottom → top
   [v0  ,  v1  ,  v2  ,  ...  ,  vk]
   v0 ≥ v1 ≥ v2 ≥ ... ≥ vk         (giảm dần)

Khi thêm value mới x:
   - Trong khi stack[-1] < x: pop (vì stack[-1] không còn cơ hội là "next greater")
   - Push x

Diễn giải:
   • Stack giữ các "ứng viên đang chờ next greater".
   • Khi gặp x lớn hơn top → top tìm được answer (= x) → pop.
   • Mỗi index push 1 lần, pop tối đa 1 lần → O(n) total.

Ví dụ trace với arr = [73, 74, 75, 71, 69, 72, 76]:

Bước  i   v   Action                                Stack (index, value)
─────────────────────────────────────────────────────────────────────────
init                                                []
1     0   73  push                                  [(0, 73)]
2     1   74  74 > 73 → pop (0,73), result[0]=74    [(1, 74)]
3     2   75  75 > 74 → pop (1,74), result[1]=75    [(2, 75)]
4     3   71  push                                  [(2, 75), (3, 71)]
5     4   69  push                                  [(2, 75), (3, 71), (4, 69)]
6     5   72  72 > 69 → pop (4,69), result[4]=72    [(2, 75), (3, 71), (5, 72)]
                72 > 71 → pop (3,71), result[3]=72
7     6   76  76 > 72 → pop (5,72), result[5]=76    [(6, 76)]
                76 > 75 → pop (2,75), result[2]=76

Result: [74, 75, 76, 72, 72, 76, -1]
        Mỗi index push 1× và pop ≤ 1× → O(n).

Monotonic deque (sliding window max) 

Invariant tại mọi thời điểm (deque giảm dần từ head → tail):

   head                              tail
   [i0  ,  i1  ,  i2  ,  ...  ,  ik]
   arr[i0] ≥ arr[i1] ≥ ... ≥ arr[ik]
   
   • Head luôn là MAX của window hiện tại.
   • Tail là phần tử mới nhất.

Khi window slide (thêm index r, có thể bỏ index l):
   1. Pop từ tail nếu arr[tail] ≤ arr[r]   (vô dụng - r mới hơn + lớn hơn)
   2. Push r vào tail
   3. Pop head nếu head ≤ r - k             (ngoài window)
   4. Max = arr[head]

Ví dụ trace với arr = [1, 3, -1, -3, 5, 3, 6, 7], k = 3:

i  v   deque (index)  Pop tail/head?            Max khi i≥k-1=2
──────────────────────────────────────────────────────────────────
0  1   [0]            push 0
1  3   [1]            pop 0 (arr[0]=1 ≤ 3); push 1
2 -1   [1, 2]         push 2                     arr[1]=3
3 -3   [1, 2, 3]      push 3 (head 1 vẫn ≤ 3-k=0?  
                       Không, 1 > 0, ok)         arr[1]=3
4  5   [4]            pop 3,2,1 (đều ≤ 5)       arr[4]=5
5  3   [4, 5]         push 5                     arr[4]=5
6  6   [6]            pop 5 (3 ≤ 6); pop 4 (5 ≤ 6)
                       Wait - index 4 với arr[4]=5
                       5 ≤ 6 → pop. push 6.       arr[6]=6
7  7   [7]            pop 6                      arr[7]=7

Output: [3, 3, 5, 5, 6, 7]  ✓

Invariant này giúp gỡ lỗi rất nhanh: nếu deque không còn monotonic, hoặc phần tử ở đầu deque nằm ngoài window, thì chắc chắn code có bug.

Template code 

# 1) Monotonic decreasing stack - Next Greater Element
def next_greater(arr: list[int]) -> list[int]:
    n = len(arr)
    result = [-1] * n
    stack: list[int] = []           # index, value giảm dần
    for i, v in enumerate(arr):
        while stack and arr[stack[-1]] < v:
            result[stack.pop()] = v
        stack.append(i)
    return result


# 2) Monotonic deque - Sliding Window Max
from collections import deque

def sliding_max(arr: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()         # index, value giảm dần ở head→tail
    out = []
    for i, v in enumerate(arr):
        while dq and arr[dq[-1]] <= v:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(arr[dq[0]])
    return out

Bài tự luyện cuối chương

  • LC 42 - Trapping Rain Water (cũng giải được bằng monotonic stack)
  • LC 316 - Remove Duplicate Letters
  • LC 456 - 132 Pattern
  • LC 901 - Online Stock Span
  • LC 1019 - Next Greater Node in Linked List
  • LC 1856 - Maximum Subarray Min-Product

18.1 Daily Temperatures (LC 739) - recap

Đã giải đầy đủ ở Chương 8.5. Pattern: monotonic decreasing stack, mỗi phần tử push/pop đúng 1 lần → O(n).

Code Python 3 

class Solution:
    def dailyTemperatures(self, t):
        result = [0] * len(t)
        stack = []
        for i, v in enumerate(t):
            while stack and t[stack[-1]] < v:
                j = stack.pop()
                result[j] = i - j
            stack.append(i)
        return result

Phân tích độ phức tạp

  • Thời gian: O(n).
  • Bộ nhớ: O(n) stack.

Bài tự luyện liên quan

  • LC 496 - Next Greater Element I.
  • LC 503 - Next Greater Element II (bài 18.2).

18.2 Next Greater Element II (LC 503)

Đề bài

Cho mảng vòng tròn nums. Với mỗi phần tử, tìm số đầu tiên lớn hơn nó tính theo chiều kim đồng hồ (có thể vòng lại). Không có → -1.

Ví dụ 

Input:  nums = [1, 2, 1]   → [2, -1, 2]
Giải thích: 1 (idx 0) → 2; 2 → không có; 1 (idx 2) → 2 (vòng lại).

Ràng buộc

  • 1 <= len(nums) <= 10^4
  • -10^9 <= nums[i] <= 10^9

Clarifying questions

  • Mảng có thể trùng giá trị? → Có; pattern monotonic vẫn đúng.

Hướng tiếp cận

Trick mảng vòng: duyệt 2n bước, dùng i % n để truy cập value. Stack monotonic giữ index thật (0..n-1) và chỉ pop ở vòng đầu (vì vòng 2 lan toả).

Code Python 3 

from typing import List

class Solution:
    def nextGreaterElements(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [-1] * n
        stack: list[int] = []
        for i in range(2 * n):
            cur = nums[i % n]
            while stack and nums[stack[-1]] < cur:
                result[stack.pop()] = cur
            if i < n:
                stack.append(i)
        return result

Phân tích độ phức tạp

  • Thời gian: O(n).
  • Bộ nhớ: O(n).

Bình luận

  • Bẫy: chỉ push ở vòng đầu (i < n), nếu push cả 2 vòng → output sai.

Bài tự luyện liên quan

  • LC 496 - Next Greater Element I.
  • LC 901 - Online Stock Span.

18.3 Largest Rectangle in Histogram (LC 84)

Đề bài

Cho mảng heights[] (chiều cao mỗi cột width 1). Tìm diện tích hình chữ nhật lớn nhất trong histogram.

Ví dụ 

Input:  heights = [2, 1, 5, 6, 2, 3]
Output: 10
Giải thích: chọn cột [5, 6] → 2 * 5 = 10.

Ràng buộc

  • 1 <= len(heights) <= 10^5
  • 0 <= heights[i] <= 10^4

Clarifying questions

  • All 0? → Trả 0.
  • Negative heights? → Theo đề LC: heights ≥ 0.

Hướng tiếp cận

Brute force - O(n²). Với mỗi cột i, expand sang 2 bên đến khi gặp cột thấp hơn.

Monotonic increasing stack - O(n).

Stack chứa index, các height tăng dần từ đáy lên đỉnh. Khi gặp h[i] nhỏ hơn h[stack top], đó là dấu hiệu cột top kết thúc bên phải ở i. Pop top, tính diện tích: - height = h[top]. - width = i - stack[-1] - 1 (nếu stack rỗng sau pop, width = i).

Hình minh hoạ với heights = [2, 1, 5, 6, 2, 3]:

heights:    2   1   5   6   2   3
                       █
              █        █
              █        █
              █        █   █
              █        █   █   █
          █   █    █   █   █   █
       _________________________________
              0   1   2   3   4   5

Stack tracing (sentinel -1):
i=0  h=2: push 0     stack=[0]
i=1  h=1: h[0]=2 > 1 → pop 0. height=2, width=1-(-1)-1=1, area=2
         push 1     stack=[1]
i=2  h=5: push 2     stack=[1, 2]
i=3  h=6: push 3     stack=[1, 2, 3]
i=4  h=2: h[3]=6 > 2 → pop 3. height=6, width=4-2-1=1, area=6
         h[2]=5 > 2 → pop 2. height=5, width=4-1-1=2, area=10  ★
         push 4     stack=[1, 4]
i=5  h=3: push 5     stack=[1, 4, 5]

Hết mảng. Sentinel right (i=6, h=0):
  pop 5. height=3, width=6-4-1=1, area=3
  pop 4. height=2, width=6-1-1=4, area=8
  pop 1. height=1, width=6-(-1)-1=6, area=6

Max = 10  ✓

Code Python 3 

from typing import List

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack: list[int] = [-1]      # sentinel
        max_area = 0
        for i, h in enumerate(heights):
            while stack[-1] != -1 and heights[stack[-1]] >= h:
                height = heights[stack.pop()]
                width = i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)
        # Drain stack với sentinel right = n.
        n = len(heights)
        while stack[-1] != -1:
            height = heights[stack.pop()]
            width = n - stack[-1] - 1
            max_area = max(max_area, height * width)
        return max_area

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(n).

Bình luận

  • Sentinel -1 ở đáy stack giúp công thức width = i - stack[-1] - 1 thống nhất khi pop ra hết.
  • Liên hệ: Bài LC 85 - Maximal Rectangle trên ma trận 0/1 → giải bằng cách “biến mỗi hàng thành histogram” rồi áp bài này.

Bài tự luyện liên quan

  • LC 85 - Maximal Rectangle.
  • LC 42 - Trapping Rain Water (monotonic version).
  • LC 1856 - Maximum Subarray Min-Product.

18.4 Sliding Window Maximum (LC 239)

Đề bài

Cho mảng nums và số k. Cửa sổ k phần tử trượt từ trái sang phải. Trả về max trong mỗi vị trí cửa sổ.

Ví dụ 

Input:  nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3, 3, 5, 5, 6, 7]

Ràng buộc

  • 1 <= len(nums) <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= len(nums)

Clarifying questions

  • k > len(nums)? → Theo đề: k <= len.
  • Window size cố định? → Có (sliding của size k).

Hướng tiếp cận

Brute force - O(n · k). TLE.

Monotonic Deque - O(n).

Deque chứa index, các value giảm dần từ head → tail. Khi mới đến i: 1. Pop từ tail nếu value <= nums[i] (chúng vô dụng - i mới hơn và lớn hơn). 2. Push i vào tail. 3. Pop từ head nếu index ngoài cửa sổ (dq[0] <= i - k). 4. Khi i >= k - 1, nums[dq[0]] là max.

Hình minh hoạ với nums = [1,3,-1,-3,5,3,6,7], k = 3:

i  v  deque (index)  state                       max khi i>=k-1=2
─────────────────────────────────────────────────────────────────
0  1  [0]            v=1
1  3  [1]            v=3 > 1, pop 0
2 -1  [1, 2]                                     nums[1]=3
3 -3  [1, 2, 3]      check head: 1 > 3-k=0 OK   nums[1]=3
4  5  [4]            5 > -3,-1,3 → pop tất     nums[4]=5
5  3  [4, 5]                                     nums[4]=5
6  6  [6]            6 > 3,5 → pop              nums[6]=6
7  7  [7]            7 > 6 → pop                nums[7]=7

Output: [3, 3, 5, 5, 6, 7]  ✓

Code Python 3 

from collections import deque
from typing import List

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq: deque[int] = deque()
        result: list[int] = []
        for i, v in enumerate(nums):
            while dq and nums[dq[-1]] <= v:
                dq.pop()
            dq.append(i)
            if dq[0] <= i - k:
                dq.popleft()
            if i >= k - 1:
                result.append(nums[dq[0]])
        return result

Phân tích độ phức tạp

  • Thời gian: O(n) - mỗi index push/pop tối đa 1 lần.
  • Bộ nhớ: O(k).

Bình luận

  • Bẫy: check head ngoài cửa sổ - phải dùng dq[0] <= i - k (do head có thể đã quá hạn).
  • Liên hệ: LC 1696 - Jump Game VI dùng cùng pattern monotonic deque trong DP transition.

Bài tự luyện liên quan

  • LC 1438 - Longest Continuous Subarray With Absolute Diff ≤ Limit.
  • LC 1696 - Jump Game VI.
  • LC 862 - Shortest Subarray with Sum at Least K.

18.5 Sum of Subarray Minimums (LC 907)

Đề bài

Cho mảng arr. Trả về tổng min(subarray) qua tất cả subarray liên tục. Modulo 10^9 + 7.

Ví dụ 

Input:  arr = [3, 1, 2, 4]
Output: 17
Subarrays:  [3],[1],[2],[4],[3,1],[1,2],[2,4],[3,1,2],[1,2,4],[3,1,2,4]
Mins:        3 + 1 + 2 + 4 + 1 + 1 + 2 + 1 + 1 + 1 = 17

Ràng buộc

  • 1 <= len(arr) <= 3·10^4
  • 1 <= arr[i] <= 3·10^4

Clarifying questions

  • arr rất nhỏ? → Vẫn áp pattern; mỗi phần tử là min của subarray độ dài 1.
  • Duplicate? → Cẩn thận với >= vs > để tránh đếm trùng.

Hướng tiếp cận

Insight chuyển bài:

Thay vì duyệt subarray, ta hỏi: mỗi phần tử arr[i] là min của bao nhiêu subarray?

arr[i] là min của subarray [l, r] ↔︎ l ∈ (prev_less[i], i] và r ∈ [i, next_less[i]).

Vậy, số subarray có min = arr[i] = (i - prev_less[i]) * (next_less[i] - i).

Đáp án = Σ arr[i] * (i - prev_less[i]) * (next_less[i] - i).

Tính prev_less, next_less dùng monotonic stack O(n).

Cẩn thận với duplicate: dùng strict < ở 1 phía, <= ở phía kia để tránh đếm trùng.

Code Python 3 

from typing import List

class Solution:
    MOD = 10**9 + 7

    def sumSubarrayMins(self, arr: List[int]) -> int:
        n = len(arr)
        # prev_less[i]: nearest index j < i with arr[j] < arr[i]; -1 nếu không có.
        prev_less = [-1] * n
        stack: list[int] = []
        for i in range(n):
            while stack and arr[stack[-1]] >= arr[i]:
                stack.pop()
            prev_less[i] = stack[-1] if stack else -1
            stack.append(i)
        # next_less[i]: nearest index j > i with arr[j] <= arr[i]; n nếu không có.
        next_less = [n] * n
        stack.clear()
        for i in range(n - 1, -1, -1):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()
            next_less[i] = stack[-1] if stack else n
            stack.append(i)

        result = 0
        for i in range(n):
            left = i - prev_less[i]
            right = next_less[i] - i
            result = (result + arr[i] * left * right) % self.MOD
        return result

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(n).

Bình luận

  • Duplicate handling: dùng >= cho prev (strict less ở quá khứ), > cho next (allow equal ở tương lai) - đảm bảo mỗi subarray có đúng 1 “min owner”.
  • Pattern “contribution của mỗi phần tử” mạnh - áp được cho LC 2104 (Sum of Subarray Ranges), LC 1856 (Min-Product).

Bài tự luyện liên quan

  • LC 2104 - Sum of Subarray Ranges.
  • LC 1856 - Maximum Subarray Min-Product.

18.6 Remove K Digits (LC 402)

Đề bài

Cho chuỗi số num và số k. Xoá đúng k chữ số sao cho chuỗi kết quả là số nhỏ nhất có thể (giữ thứ tự các chữ số còn lại). Bỏ leading zero, chuỗi rỗng trả "0".

Ví dụ 

Input:  num = "1432219", k = 3   → "1219"
Input:  num = "10200", k = 1     → "200"
Input:  num = "10", k = 2        → "0"

Ràng buộc

  • 1 <= k <= len(num) <= 10^5
  • num chỉ chứa digit, không leading zero (trừ “0”)

Clarifying questions

  • k = len(num)? → Trả “0”.
  • Leading zero? → Phải bỏ.

Hướng tiếp cận

Greedy + Monotonic increasing stack.

Duyệt num. Với mỗi digit d: - Trong khi stack không rỗng, top > d, và k > 0: pop top (xoá nó tốt hơn vì làm số nhỏ đi). - Push d.

Cuối: nếu còn k > 0 (chưa đủ xoá) → pop từ cuối stack (digit ở cuối luôn lớn nhất trong số còn lại, vì stack đang increasing).

Cuối cùng: bỏ leading zero, return.

Hình minh hoạ với num = "1432219", k = 3:

digit  stack       k    action
─────────────────────────────────────────────────────
'1'    [1]         3    push
'4'    [1, 4]      3    push (4 > top)
'3'    [1, 3]      2    pop 4 (4 > 3, k>0). push 3
'2'    [1, 2]      1    pop 3 (3 > 2). push 2
'2'    [1, 2, 2]   1    push
'1'    [1, 1]      0    pop 2 (2 > 1). push 1
'9'    [1, 1, 9]   0    push (k=0, không pop được)

Còn 7-0=7 digit chứ không, nguyên thuỷ 7 digit, k=3, kết quả phải 4 digit.
stack chứa [1, 1, 9]. Cộng với cái cuối '1' đã pop... wait, recount.

Actually 1432219 length=7, k=3, output length=4.
Let me redo more carefully:

i=0 '1': stack=[1]
i=1 '4': 4 > 1, push. stack=[1,4]
i=2 '3': 4 > 3, k=3 → pop. stack=[1]. now stack[-1]=1 < 3, push. stack=[1,3] k=2
i=3 '2': 3 > 2, k=2 → pop. stack=[1]. 1 < 2, push. stack=[1,2] k=1
i=4 '2': 2 not > 2, push. stack=[1,2,2]
i=5 '1': 2 > 1, k=1 → pop. stack=[1,2]. 2 > 1, k=0 → stop. push. stack=[1,2,1]
i=6 '9': k=0, no pop. push. stack=[1,2,1,9]

len=4 OK. Result "1219". ✓

Code Python 3 

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        stack: list[str] = []
        for d in num:
            while k > 0 and stack and stack[-1] > d:
                stack.pop()
                k -= 1
            stack.append(d)
        # Còn k? Pop từ cuối (digit lớn nhất nếu stack tăng).
        while k > 0:
            stack.pop()
            k -= 1
        # Bỏ leading zero.
        result = ''.join(stack).lstrip('0')
        return result if result else '0'

Phân tích độ phức tạp

  • Thời gian: O(n). Bộ nhớ: O(n).

Bình luận

  • Greedy justification: Khi gặp digit nhỏ hơn top, pop top → số nhỏ đi ngay tại vị trí cao hơn → giảm giá trị tổng nhiều nhất.
  • Bẫy: quên xử lý leading zero. "10200" k=1 → stack [1, 0, 2, 0, 0], pop 1 → "0200", strip leading → "200".

Bài tự luyện liên quan

  • LC 316 - Remove Duplicate Letters.
  • LC 321 - Create Maximum Number.
  • LC 1081 - Smallest Subsequence of Distinct Characters.

Tóm tắt chương & Quyết định

Largest Rectangle (LC 84) - sentinel trace

Input: heights = [2, 1, 5, 6, 2, 3], thêm sentinel 0 cuối.

i  h[i]  stack (idx)   pop & compute       maxA
0   2    [0]                                0
1   1    pop 0: h=2, w=1-0  ⇒ 2             2
         [1]
2   5    [1,2]                              2
3   6    [1,2,3]                            2
4   2    pop 3: h=6, w=4-2-1=1 ⇒ 6          6
         pop 2: h=5, w=4-1-1=2 ⇒ 10        10
         [1,4]
5   3    [1,4,5]                           10
6   0    pop 5: h=3, w=6-4-1=1 ⇒ 3
         pop 4: h=2, w=6-1-1=4 ⇒ 8
         pop 1: h=1, w=6     ⇒ 6           10

Invariant: stack lưu các index có h tăng nghiêm ngặt; khi gặp h thấp hơn, các cột bên trái cao hơn “đóng cửa” rectangle của chúng.

Sum of Subarray Minimums (LC 907) - contribution proof

Mỗi a[i] đóng góp a[i] × left × right lần làm minimum, với: - left[i] = số phần tử bên trái mà a[i] vẫn là min (kể cả chính i). - right[i] = tương tự bên phải. - Tie-break: dùng < bên trái, ≤ bên phải (hoặc ngược) để mỗi subarray min đếm đúng 1 lần.

Remove K Digits (LC 402) - greedy proof

  • Nếu trong stack đỉnh s[-1] > d_in (digit mới): xóa s[-1] luôn tốt hơn vì vị trí nó bên trái có trọng số hàng cao hơn, “xóa số lớn ở vị trí trái” giảm giá trị nhiều hơn xóa ở vị trí phải.