1.1 Stack vs Queue — Hai triết lý

Khi nào dùng cái nào?

• Stack: matching cặp, recursion thay thế, monotonic sequence, undo history.
• Queue: BFS, lập lịch FIFO, level-order traversal trên cây.

1.2 Stack trong Python — list

Python dùng list làm stack qua append và pop:

stack = []
stack.append(x)        # push      O(1) amortised
stack.pop()            # pop top   O(1)
stack[-1]              # peek      O(1)
len(stack) == 0        # check empty

Bẫy phổ biến

stack[0]               # SAI — đây là bottom, không phải top
stack.pop(0)           # SAI — pop ở đầu là O(n), không phải O(1)

1.3 Queue trong Python — collections.deque

list.pop(0) là O(n) → không phù hợp cho queue. Dùng deque:

from collections import deque
q = deque()
q.append(x)            # enqueue   O(1)
q.popleft()            # dequeue   O(1)
q[0]                   # front     O(1)

# deque cũng hỗ trợ thao tác hai đầu:
q.appendleft(x)        # O(1)
q.pop()                # O(1) — pop ở phải

Tại sao deque mạnh?

Deque cài đặt bằng doubly linked list của block. Mọi thao tác ở hai đầu là O(1). Đây cũng là cấu trúc dùng cho Monotonic Deque (Phần 4).

1.4 Bảng tổng hợp Big-O

Đa số bài thuật toán không quan tâm "truy cập index giữa" — nên deque ổn cho cả stack và queue. Tuy nhiên, vì list nhẹ hơn, đa số code Python idiom dùng list cho stack thuần và deque chỉ khi cần thao tác hai đầu.

2.1 Pattern: Matching Pairs với Stack

Ba câu hỏi cần trả lời

1. Cái gì coi là "mở" → push.
2. Cái gì coi là "đóng" → pop và kiểm tra.
3. Trạng thái cuối hợp lệ là gì? (thường: stack rỗng).

Pattern này áp dụng cho: parentheses, brackets, HTML tags, function call simulation, undo/redo, expression evaluation.

2.2 Worked Example 1 — Valid Parentheses

Đề (LeetCode #20): Cho string chỉ gồm ()[]{}. Trả True nếu mọi ngoặc khớp đúng.

def isValid(s):
    pair = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in s:
        if ch in '([{':
            stack.append(ch)
        else:
            if not stack or stack[-1] != pair[ch]:
                return False
            stack.pop()
    return len(stack) == 0

Trace với "({[]})"

Stack rỗng → True. Time O(n), Space O(n).

2.3 Worked Example 2 — Min Stack (Design)

Đề (LeetCode #155): Thiết kế stack hỗ trợ thêm getMin() trong O(1).

Thách thức

Stack thường có push/pop/top O(1), nhưng tìm min là O(n). Làm sao biến min cũng thành O(1)?

Approach: Stack phụ lưu min

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []           # đỉnh = min hiện tại

    def push(self, x):
        self.stack.append(x)
        m = min(x, self.min_stack[-1] if self.min_stack else x)
        self.min_stack.append(m)

    def pop(self):
        self.stack.pop()
        self.min_stack.pop()

    def top(self):
        return self.stack[-1]

    def getMin(self):
        return self.min_stack[-1]

Mọi thao tác O(1). Space O(n).

2.4 Worked Example 3 — Evaluate Reverse Polish Notation

Đề (LeetCode #150): Tính giá trị biểu thức RPN.

Ví dụ: ["2","1","+","3","*"] = (2+1) * 3 = 9.

def evalRPN(tokens):
    stack = []
    ops = {'+', '-', '*', '/'}
    for t in tokens:
        if t in ops:
            b = stack.pop()
            a = stack.pop()
            if t == '+': stack.append(a + b)
            elif t == '-': stack.append(a - b)
            elif t == '*': stack.append(a * b)
            else: stack.append(int(a / b))     # Python truncate khác C++
        else:
            stack.append(int(t))
    return stack[0]

Quan sát

RPN là dạng "tự nhiên" cho stack: số → push, toán tử → pop 2 số, tính, push lại. Không có ngoặc, không có ưu tiên — đơn giản hoá hoàn toàn.

Time O(n), Space O(n).

Knowledge Check — Stack Basics

3.1 Monotonic Stack là gì?

Hai biến thể

Mỗi phần tử push 1 lần, pop tối đa 1 lần

→ Tổng số thao tác qua toàn thuật toán ≤ 2n → O(n) (phân tích amortised).

3.2 Tín hiệu nhận biết Monotonic Stack

Khi đọc đề, các "mùi" sau gợi ý mạnh:

3.3 Worked Example 4 — Daily Temperatures

Đề (LeetCode #739): Mảng temps. Trả mảng res với res[i] = số ngày phải chờ đến ngày có nhiệt độ cao hơn. 0 nếu không có.

Ví dụ: [73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0].

Brute force

Với mỗi i, scan j > i tìm temp lớn hơn → O(n²). Với n = 10⁵ → TLE.

Monotonic Stack (Decreasing)

def dailyTemperatures(temps):
    res = [0] * len(temps)
    stack = []                          # lưu index
    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            j = stack.pop()
            res[j] = i - j              # tìm thấy "next greater"
        stack.append(i)
    return res

Time O(n), Space O(n).

3.4 Daily Temperatures — Trace tay

temps = [73, 74, 75, 71, 69, 72, 76, 73]

Index còn trên stack ([6,7]) là không có "next greater" → res = 0.

3.5 Vì sao Monotonic Stack là O(n)? Phân tích amortised

Lo lắng: vòng while bên trong for có thể tốn nhiều bước → tổng có thể O(n²)?

Lập luận

Mỗi index i:

• Được push lên stack đúng 1 lần.
• Được pop khỏi stack tối đa 1 lần.

Tổng số thao tác push + pop qua n vòng for ≤ 2n. Do đó tổng thời gian là O(n) bất kể vòng while có vẻ tốn nhiều.

3.6 Worked Example 5 — Next Greater Element II (Circular)

Đề (LeetCode #503): Mảng circular (vòng tròn). Tìm next greater cho mỗi phần tử. Nếu không có, trả -1.

Ví dụ: [1,2,1] → [2,-1,2] (phần tử cuối quay lại từ đầu).

Mẹo "duyệt mảng 2 lần"

Để mô phỏng vòng tròn, duyệt index từ 0 đến 2n−1, dùng i % n để truy cập:

def nextGreaterElements(nums):
    n = len(nums)
    res = [-1] * n
    stack = []
    for i in range(2 * n):
        x = nums[i % n]
        while stack and nums[stack[-1]] < x:
            res[stack.pop()] = x
        if i < n:                          # chỉ push trong vòng đầu
            stack.append(i)
    return res

Time O(n), Space O(n).

3.7 Worked Example 6 — Largest Rectangle in Histogram

Đề (LeetCode #84, Hard): Mảng heights các cột. Tìm hình chữ nhật diện tích lớn nhất chứa trong histogram.

Ví dụ: [2,1,5,6,2,3] → 10 (cột 5 và 6 cao 5 → 5×2 = 10).

Quan sát then chốt

Hình chữ nhật lớn nhất "đặt trên" cột i có:

• Chiều cao = heights[i].
• Chiều rộng = khoảng cách từ cột thấp hơn gần nhất bên trái đến cột thấp hơn gần nhất bên phải.

"Cột thấp hơn gần nhất" = bài Next Smaller. Dùng Monotonic Increasing Stack.

def largestRectangleArea(heights):
    stack = []                              # index, monotonic increasing
    best = 0
    heights.append(0)                       # sentinel để đẩy hết stack ở cuối
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            top = stack.pop()
            left = stack[-1] if stack else -1
            width = i - left - 1
            best = max(best, heights[top] * width)
        stack.append(i)
    return best

3.8 Largest Rectangle — Phân tích chi tiết

Vai trò sentinel heights.append(0)

Sau vòng for thường, stack có thể còn phần tử (các cột chưa "gặp cột thấp hơn"). Append 0 ở cuối buộc mọi cột pop ra để xử lý. Không có sentinel sẽ cần xử lý sau vòng for.

Vì sao width = i - left - 1?

Khi pop top:

• i là cột thấp hơn gần nhất bên phải của top.
• stack[-1] (nếu có) là cột thấp hơn gần nhất bên trái.
• Cột top "thống trị" toàn bộ khoảng (left, i), tức i − left − 1 cột.

Trace với [2,1,5,6,2,3,0] (đã append sentinel)

3.9 Worked Example 7 — Trapping Rain Water (Monotonic Stack)

Tuần 2 đã giải #42 bằng Prefix Max O(n) time, O(n) space. Giờ giải bằng Monotonic Stack — đây là approach phổ biến trong phỏng vấn.

Ý tưởng — "Vũng nước" giữa hai cột cao

Duy trì decreasing stack các index. Khi gặp cột cao hơn đỉnh stack, phần "vũng" được tính:

def trap(height):
    stack = []
    water = 0
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()
            if not stack: break
            left = stack[-1]
            width = i - left - 1
            bounded_height = min(height[left], h) - height[bottom]
            water += width * bounded_height
        stack.append(i)
    return water

Time O(n), Space O(n) — cùng O(n) như Prefix Max nhưng tinh thần khác.

3.10 Trapping Rain Water — Two Pointer O(1) Space

Approach thứ ba, O(1) space, kết hợp tinh thần Container With Most Water (Tuần 2):

def trap(height):
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    return water

Trực giác

Tại mỗi bước, dịch pointer của bên thấp hơn — vì bên đó "biết" nước có thể đọng đến đâu (giới hạn bởi left_max hoặc right_max đã thấy). Bên cao hơn vẫn còn "chưa chắc" — không thể quyết định.

Cùng tinh thần "luôn dịch cột thấp hơn" như Container With Most Water.

Knowledge Check — Monotonic Stack

4.1 Vì sao cần Deque, không phải Stack?

Monotonic Stack chỉ thao tác một đầu (top). Nhưng có bài cần thao tác cả hai đầu:

• Đầu trái: bỏ phần tử khi cửa sổ trượt qua.
• Đầu phải: thêm phần tử mới + duy trì monotonic.

Đây là khi collections.deque phát huy: O(1) cả hai đầu.

Kết hợp Sliding Window (Tuần 4) + Monotonic — bài Sliding Window Maximum

Bài này là "boss" của tuần — kết hợp 2 tuần kỹ thuật:

• Sliding Window: cửa sổ size k.
• Monotonic Deque: lưu các "ứng viên" có thể là max hiện tại.

4.2 Worked Example 8 — Sliding Window Maximum

Đề (LeetCode #239, Hard): Mảng nums, số k. Trả mảng max của mọi cửa sổ size k.

Constraints: 1 ≤ n ≤ 10⁵ → cần O(n).

Brute force

Với mỗi cửa sổ, tìm max → O(n × k). Với n,k = 10⁵ → TLE.

Monotonic Decreasing Deque

from collections import deque
def maxSlidingWindow(nums, k):
    dq = deque()                       # lưu index, decreasing theo nums[index]
    res = []
    for i, x in enumerate(nums):
        # 1. Bỏ index ngoài cửa sổ ở đầu trái
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # 2. Duy trì monotonic decreasing — pop các phần tử nhỏ hơn x ở phải
        while dq and nums[dq[-1]] < x:
            dq.pop()
        # 3. Thêm i ở phải
        dq.append(i)
        # 4. Đầu trái = max của cửa sổ hiện tại
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res

Time O(n), Space O(k).

4.3 Sliding Window Maximum — Trace tay

nums = [1,3,-1,-3,5,3,6,7], k = 3. Kỳ vọng: [3,3,5,5,6,7].

Kết quả: [3,3,5,5,6,7].

5.1 Pattern Queue + BFS (Preview)

from collections import deque
q = deque([start])
visited = {start}
while q:
    node = q.popleft()
    for neighbor in neighbors(node):
        if neighbor not in visited:
            visited.add(neighbor)
            q.append(neighbor)

FIFO của queue đảm bảo BFS thăm nodes theo thứ tự khoảng cách từ start tăng dần. Đây là nền tảng của:

• Tìm shortest path trong unweighted graph.
• Level-order traversal trên cây (Tuần 8).
• Multi-source BFS (Rotting Oranges, Walls and Gates).
• Topological Sort (Kahn's algorithm — Tuần 10).

Tuần 10 sẽ đào sâu — tuần này chỉ giới thiệu để sinh viên không bỡ ngỡ với deque.

5.2 Worked Example 9 — Implement Queue using Stacks

Đề (LeetCode #232): Cài queue chỉ dùng 2 stack. push, pop, peek, empty. pop và peek cần O(1) amortised.

class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []

    def push(self, x):
        self.in_stack.append(x)

    def pop(self):
        self._move()
        return self.out_stack.pop()

    def peek(self):
        self._move()
        return self.out_stack[-1]

    def empty(self):
        return not self.in_stack and not self.out_stack

    def _move(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

Phân tích amortised

Mỗi phần tử được "di chuyển" giữa hai stack tối đa 1 lần (in → out). Push O(1) thường; pop/peek O(1) amortised vì khi _move tốn O(n), nó chỉ xảy ra khi out_stack rỗng.

Tổng kết Tuần 6

Đã học

• Stack basics: matching pairs (Valid Parentheses), design (Min Stack), evaluate (RPN).
• Monotonic Stack: pattern then chốt cho next greater/smaller; phân tích amortised O(n); sentinel trick; mẹo "duyệt 2 lần" cho circular array.
• Boss-level: Largest Rectangle in Histogram (Hard) — quan sát "cột thấp hơn gần nhất bên trái/phải".
• Trapping Rain Water — 3 cách: Prefix Max (Tuần 2), Monotonic Stack, Two Pointer O(1).
• Monotonic Deque: Sliding Window Maximum — kết hợp Tuần 4 và tuần này.
• Queue Design: Implement Queue using Stacks — tinh thần amortised + cấu trúc phụ.
• BFS preview: chuẩn bị cho Tuần 10.

Bài về nhà (12 bài)

1. LeetCode #20 — Valid Parentheses
2. LeetCode #155 — Min Stack
3. LeetCode #150 — Evaluate Reverse Polish Notation
4. LeetCode #739 — Daily Temperatures
5. LeetCode #496 — Next Greater Element I
6. LeetCode #503 — Next Greater Element II (circular)
7. LeetCode #84 — Largest Rectangle in Histogram (Hard)
8. LeetCode #42 — Trapping Rain Water (cả 3 approach)
9. LeetCode #239 — Sliding Window Maximum (Hard, boss)
10. LeetCode #232 — Implement Queue using Stacks
11. LeetCode #225 — Implement Stack using Queues (chiều ngược)
12. LeetCode #901 — Online Stock Span (monotonic stack streaming)