03-Monotonic-Stack-Queue

Buổi 03 — Monotonic Stack & Queue

Navigation

← 02-Bit-Manipulation | → 04-Advanced-Binary-Search Giai đoạn: FAANG Mastery | Độ khó: ⭐⭐⭐⭐

---

1. Analogy & Context

Nightclub Bouncer Analogy

Monotonic Stack = bouncer tại một nightclub duy trì “VIP list” theo thứ tự nghiêm ngặt.

• Khách mới đến: bouncer kiểm tra list từ cuối
• Ai “kém VIP hơn” (nhỏ hơn/lớn hơn tùy variant) → bị đuổi ra ngoài
• Khách mới vào cuối list
• Kết quả: list luôn được sắp xếp theo mức độ VIP

Ý nghĩa thuật toán: khi ta “đuổi” một phần tử ra khỏi stack, ta đã biết được “next greater element” của nó (chính là phần tử mới đến gây ra việc đuổi đó).

Tại sao Monotonic Stack quan trọng?

Bài toán “next greater element” bằng naive approach cần $O(N^2)$ — với mỗi element, duyệt toàn bộ array còn lại. Monotonic stack giải quyết trong $O(N)$ — mỗi element chỉ được push/pop đúng một lần.

FAANG Signal

Google, Meta thường hỏi Trapping Rain Water (#42) và Largest Rectangle in Histogram (#84) — cả hai đều có solution tối ưu bằng monotonic stack. Sliding Window Maximum (#239) là câu hỏi phổ biến của Amazon.

Hai variants chính:

• Monotonic Stack: xử lý problems liên quan đến “next/previous greater/smaller element”
• Monotonic Deque (double-ended queue): xử lý sliding window maximum/minimum

---

2. The FAANG Standard

Problem Pattern	Naive	Monotonic	Speedup
Next greater element	$O(N^2)$	$O(N)$	N×
Largest rectangle	$O(N^2)$	$O(N)$	N×
Sliding window max	$O(NK)$	$O(N)$	K×
Trapping rain water	$O(N^2)$	$O(N)$	N×

Khi nào dùng Increasing vs Decreasing:

Stack Type	Duy trì	Dùng cho
Monotonic Increasing	Bottom lớn nhất	”Next smaller element”, histogram
Monotonic Decreasing	Bottom nhỏ nhất	”Next greater element”, temperatures

Quick Decision

• “Next GREATER” → dùng decreasing stack (pop khi gặp phần tử lớn hơn)
• “Next SMALLER” → dùng increasing stack (pop khi gặp phần tử nhỏ hơn)

---

3. Visual Thinking (Mermaid)

3.1 Next Greater Element — Processing [2, 1, 5, 6, 2, 3]

sequenceDiagram
    participant A as Array
    participant S as Stack (decreasing)
    participant R as Result

    Note over A: Process 2
    A->>S: push index 0 (val=2)
    Note over S: [0]

    Note over A: Process 1
    A->>S: 1 < 2, push index 1 (val=1)
    Note over S: [0, 1]

    Note over A: Process 5
    A->>S: 5 > 1 → pop idx 1, result[1]=5
    A->>S: 5 > 2 → pop idx 0, result[0]=5
    A->>S: push index 2 (val=5)
    Note over S: [2]
    Note over R: result[0]=5, result[1]=5

    Note over A: Process 6
    A->>S: 6 > 5 → pop idx 2, result[2]=6
    A->>S: push index 3 (val=6)
    Note over R: result[2]=6

    Note over A: Process 2
    A->>S: 2 < 6, push index 4
    Note over S: [3, 4]

    Note over A: Process 3
    A->>S: 3 > 2 → pop idx 4, result[4]=3
    A->>S: 3 < 6, push index 5
    Note over S: [3, 5]
    Note over R: result[4]=3

    Note over A: End — remaining [3,5] → result=-1
    Note over R: Final: [5,5,6,-1,3,-1]

3.2 Sliding Window Max — Monotonic Deque

flowchart LR
    subgraph "nums = [1,3,-1,-3,5,3,6,7], k=3"
        direction LR
        W1["Window [1,3,-1]<br/>Deque: [3]<br/>Max = 3"]
        W2["Window [3,-1,-3]<br/>Deque: [3,-1,-3]<br/>Max = 3"]
        W3["Window [-1,-3,5]<br/>Deque: [5]<br/>Max = 5"]
        W4["Window [-3,5,3]<br/>Deque: [5,3]<br/>Max = 5"]
        W5["Window [5,3,6]<br/>Deque: [6]<br/>Max = 6"]
        W6["Window [3,6,7]<br/>Deque: [7]<br/>Max = 7"]
    end
    W1 --> W2 --> W3 --> W4 --> W5 --> W6

Deque Rule

Khi thêm phần tử mới vào deque: xóa tất cả phần tử ở CUỐI nhỏ hơn phần tử mới (chúng không bao giờ là max). Khi window slide: xóa phần tử ở ĐẦU nếu index của nó đã ra ngoài window.

---

4. TypeScript Template

4.1 Next Greater Element — O(N)

// LeetCode #496 (variant)
// Monotonic decreasing stack: stack stores indices, values decrease from bottom to top
function nextGreaterElement(nums: number[]): number[] {
    const n = nums.length;
    const result = new Array(n).fill(-1);
    const stack: number[] = [];     // stores INDICES (not values!)
 
    for (let i = 0; i < n; i++) {
        // Pop all elements smaller than nums[i]
        // Their "next greater element" is nums[i]
        while (stack.length > 0 && nums[stack[stack.length - 1]] < nums[i]) {
            const idx = stack.pop()!;
            result[idx] = nums[i];  // found next greater for idx
        }
        stack.push(i);
    }
    // Remaining indices in stack → no next greater → result stays -1
    return result;
}
 
// Time: O(N) — each element pushed and popped at most once
// Space: O(N) — stack in worst case (decreasing array)

4.2 Daily Temperatures — O(N)

// LeetCode #739
// "How many days until a warmer temperature?"
// Same pattern as next greater, but store DISTANCES
function dailyTemperatures(temperatures: number[]): number[] {
    const n = temperatures.length;
    const result = new Array(n).fill(0);
    const stack: number[] = [];     // monotonic decreasing stack of indices
 
    for (let i = 0; i < n; i++) {
        while (
            stack.length > 0 &&
            temperatures[stack[stack.length - 1]] < temperatures[i]
        ) {
            const prevDay = stack.pop()!;
            result[prevDay] = i - prevDay;  // distance = current index - prev index
        }
        stack.push(i);
    }
    return result;
}
 
// Example: [73, 74, 75, 71, 69, 72, 76, 73]
// Result:  [1,   1,   4,   2,   1,   1,   0,  0]
// Day 0 (73°): next warmer is day 1 (74°) → wait 1 day
// Day 2 (75°): next warmer is day 6 (76°) → wait 4 days

4.3 Largest Rectangle in Histogram — O(N)

// LeetCode #84
// Approach: monotonic increasing stack. When a shorter bar is encountered,
// pop taller bars and calculate max rectangle using them as height.
function largestRectangleInHistogram(heights: number[]): number {
    const stack: number[] = [];     // monotonic increasing stack of indices
    let maxArea = 0;
 
    // Add sentinel 0 at end to flush all remaining bars
    const h = [...heights, 0];
 
    for (let i = 0; i < h.length; i++) {
        while (stack.length > 0 && h[stack[stack.length - 1]] > h[i]) {
            const height = h[stack.pop()!];
            // Width: from current stack top (exclusive) to i (exclusive)
            const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
 
    return maxArea;
}
 
// Example: heights = [2, 1, 5, 6, 2, 3]
// Max rectangle = 10 (bars 5,6 with width 2, height 5)
// Or bars 2,1,5,6,2,3 with height 2 and width 5 = 10 ✓

4.4 Trapping Rain Water — Stack Approach, O(N)

// LeetCode #42
// Approach: when we find a taller bar (right wall), the top of stack is the "pit"
// and the new stack top is the left wall. Calculate trapped water.
function trap(height: number[]): number {
    const stack: number[] = [];
    let totalWater = 0;
 
    for (let i = 0; i < height.length; i++) {
        while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
            const bottom = stack.pop()!;        // the pit (lowest bar)
 
            if (stack.length === 0) break;       // no left wall
 
            const left = stack[stack.length - 1];
            const right = i;
 
            const boundedHeight = Math.min(height[left], height[right]) - height[bottom];
            const width = right - left - 1;
            totalWater += boundedHeight * width;
        }
        stack.push(i);
    }
 
    return totalWater;
}
 
// Example: height = [0,1,0,2,1,0,1,3,2,1,2,1]
// Water = 6
// Intuition: water fills "containers" formed by taller walls on both sides

4.5 Sliding Window Maximum — Monotonic Deque, O(N)

// LeetCode #239
// Deque stores indices in decreasing order of values.
// Front of deque is always the maximum of the current window.
// Pattern: dùng `head` index pointer thay cho deque.shift() để giữ O(1) eviction
// từ front. deque.pop() từ back vẫn là O(1) — không cần đổi.
// Xem 03-Stack-and-Queue § Pitfall 2 để biết vì sao .shift() là O(N).
function maxSlidingWindow(nums: number[], k: number): number[] {
    const deque: number[] = [];     // stores indices, values decrease front→back
    let head = 0;                   // index pointer cho "front" của deque
    const result: number[] = [];
 
    for (let i = 0; i < nums.length; i++) {
        // Step 1: Remove indices that are out of window [i-k+1, i]
        if (head < deque.length && deque[head] < i - k + 1) {
            head++;                 // O(1) — không re-index như shift()
        }
 
        // Step 2: Remove indices from BACK whose values <= nums[i]
        // (they can never be the max while nums[i] is in the window)
        while (head < deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();            // remove from back — O(1) là an toàn
        }
 
        deque.push(i);              // add current index to back
 
        // Step 3: Record result once window is fully formed
        if (i >= k - 1) {
            result.push(nums[deque[head]]);    // front is always max
        }
    }
 
    return result;
}
 
// Time:  O(N) — each element enqueued and dequeued at most once
// Space: O(k) — deque holds at most k elements

---

5. Complexity Deep-dive

Amortized O(N) Analysis

Tại sao monotonic stack là O(N) dù có vòng while lồng nhau?

Mỗi element được push đúng 1 lần và pop đúng 1 lần. Tổng số push + pop = 2N. → Amortized O(1) per element → O(N) total.

Algorithm	Time	Space	Naive vs Optimal
Next Greater Element	$O(N)$	$O(N)$	vs $O(N^2)$ naive
Daily Temperatures	$O(N)$	$O(N)$	vs $O(N^2)$ naive
Largest Rectangle	$O(N)$	$O(N)$	vs $O(N^2)$ divide/naive
Trapping Rain Water	$O(N)$	$O(N)$	vs $O(N^2)$ naive
Sliding Window Max	$O(N)$	$O(k)$	vs $O(NK)$ naive

Deque Sliding Window chi tiết:

• Naive: với mỗi window, tìm max trong O(K) → O(NK) total
• Deque: mỗi element vào/ra deque đúng 1 lần → O(N) total
• Speedup factor: K lần (với K=1000, N=10^5, tiết kiệm 10^8 operations!)

---

6. Edge Cases & Pitfalls

Increasing vs Decreasing Stack — Nhầm Là Sai

• Monotonic DECREASING stack (pop khi element mới lớn hơn top): dùng cho “next GREATER element”
• Monotonic INCREASING stack (pop khi element mới nhỏ hơn top): dùng cho “next SMALLER element” và histogram

Nhớ: “đuổi” phần tử khi tìm thấy đối thủ “mạnh hơn” nó (theo chiều bài muốn).

Strictly Greater vs Greater-or-Equal

Điều kiện pop ảnh hưởng đến handling của equal elements:

// For next STRICTLY greater (not equal):
while (stack.length > 0 && nums[stack[stack.length-1]] < nums[i]) // strict <
 
// For next greater-or-equal:
while (stack.length > 0 && nums[stack[stack.length-1]] <= nums[i]) // <=

Equal elements trong histogram: dùng > để không pop equal bars — chỉ pop khi gặp shorter bar.

Store Indices, Not Values

Hầu hết monotonic stack problems cần indices (để tính width/distance), không phải values.

// Wrong:
stack.push(nums[i]);        // lost position info!
 
// Correct:
stack.push(i);              // store index, access value via nums[i]

Sentinel Values

Trong Largest Rectangle in Histogram, thêm 0 vào cuối array giúp flush toàn bộ stack khi kết thúc. Không có sentinel, phải xử lý remaining elements sau loop — dễ quên.

Deque: Remove Out-of-Window từ Front

Trong sliding window max, PHẢI kiểm tra và remove front khi index ra ngoài window TRƯỚC KHI record result. Dùng head index pointer thay cho .shift() — .shift() là O(N) (xem 03-Stack-and-Queue § Pitfall 2):

if (head < deque.length && deque[head] < i - k + 1) head++;
// ...
result.push(nums[deque[head]]);   // now safe to use front

---

7. Pattern Recognition

Khi Nào Dùng Monotonic Stack/Queue

“Next greater element” → Monotonic decreasing stack → Pop khi tìm thấy phần tử lớn hơn; popped element = “phần tử cần trả lời”

“Daily temperatures / wait for warmer day” → Monotonic decreasing stack → Cùng pattern, lưu index để tính khoảng cách

“Largest rectangle in histogram” → Monotonic increasing stack → Pop khi gặp bar ngắn hơn; tính diện tích với height=popped bar

“Trapping rain water” → Monotonic stack hoặc two-pointer → Stack approach: tính water layer-by-layer theo chiều ngang

“Sliding window maximum/minimum” → Monotonic deque → Deque stores valid candidates, front is always current max

“Stock span” → Monotonic decreasing stack → Span = distance đến previous greater element

“Remove k digits to make smallest number” → Monotonic increasing stack → Giữ monotonic increasing bằng cách remove lớn hơn digit mới

“Verify preorder traversal of BST” → Monotonic stack → Simulate traversal

---

8. Top LeetCode Problems

#	Problem	Difficulty	Pattern
LC-739 #739	Daily Temperatures	Medium	Decreasing stack
LC-496 #496	Next Greater Element I	Easy	Decreasing stack
LC-503 #503	Next Greater Element II (circular)	Medium	Stack + modulo
LC-84 #84	Largest Rectangle in Histogram	Hard	Increasing stack
LC-239 #239	Sliding Window Maximum	Hard	Monotonic deque
LC-42 #42	Trapping Rain Water	Hard	Stack or two-pointer
LC-901 #901	Online Stock Span	Medium	Decreasing stack
LC-402 #402	Remove K Digits	Medium	Increasing stack

Complete Solution: #239 Sliding Window Maximum

// LeetCode #239 — Sliding Window Maximum
// Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
// Output: [3,3,5,5,6,7]
 
function maxSlidingWindowComplete(nums: number[], k: number): number[] {
    const n = nums.length;
    const result: number[] = [];
    // Deque stores INDICES. Values at those indices are in DECREASING order.
    // deque[head] is always the index of the current window's maximum.
    // Dùng `head` index pointer cho front (O(1)) — KHÔNG dùng .shift() (O(N)).
    const deque: number[] = [];
    let head = 0;
 
    for (let i = 0; i < n; i++) {
        // ── STEP 1: Evict index that fell outside the window ──────────────────
        // Window = [i - k + 1, i]. If front index < i-k+1, it's stale.
        if (head < deque.length && deque[head] < i - k + 1) {
            head++;
        }
 
        // ── STEP 2: Maintain decreasing order in deque ────────────────────────
        // Remove all indices from BACK whose values are <= nums[i].
        // Why? They are DOMINATED: nums[i] is larger AND more recent.
        //      They will never become the window max while nums[i] is present.
        while (head < deque.length && nums[deque[deque.length - 1]] <= nums[i]) {
            deque.pop();
        }
        deque.push(i);
 
        // ── STEP 3: Record result once first window is complete ───────────────
        if (i >= k - 1) {
            result.push(nums[deque[head]]);    // front index → maximum value
        }
    }
 
    return result;
}
 
/*
TRACE for nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3:
 
i=0, nums[0]=1:
  Deque: [] → push 0
  Deque: [0]  (values: [1])
  i < k-1=2, no result yet
 
i=1, nums[1]=3:
  Front check: 0 >= 1-3+1=-1, ok
  Back removal: nums[0]=1 <= 3 → pop 0
  Deque: [] → push 1
  Deque: [1]  (values: [3])
  i < 2, no result yet
 
i=2, nums[2]=-1:
  Front check: 1 >= 2-3+1=0, ok
  Back removal: nums[1]=3 > -1, stop
  Push 2
  Deque: [1, 2]  (values: [3, -1])
  i == k-1=2 → result = [nums[1]] = [3]
 
i=3, nums[3]=-3:
  Front check: 1 >= 3-3+1=1, ok (barely)
  Back removal: nums[2]=-1 > -3, stop
  Push 3
  Deque: [1, 2, 3]  (values: [3, -1, -3])
  i >= 2 → result = [3, nums[1]=3]
 
i=4, nums[4]=5:
  Front check: 1 < 4-3+1=2 → EVICT front (1)
  Deque: [2, 3]
  Back removal: nums[3]=-3 <= 5 → pop 3
                nums[2]=-1 <= 5 → pop 2
  Deque: [] → push 4
  Deque: [4]  (values: [5])
  result = [3, 3, nums[4]=5]
 
i=5, nums[5]=3:
  Front check: 4 >= 5-3+1=3, ok
  Back removal: nums[4]=5 > 3, stop
  Push 5
  Deque: [4, 5]  (values: [5, 3])
  result = [3, 3, 5, nums[4]=5]
 
i=6, nums[6]=6:
  Front check: 4 >= 6-3+1=4, ok (barely)
  Back removal: nums[5]=3 <= 6 → pop 5
                nums[4]=5 <= 6 → pop 4
  Deque: [] → push 6
  Deque: [6]  (values: [6])
  result = [3, 3, 5, 5, nums[6]=6]
 
i=7, nums[7]=7:
  Front check: 6 >= 7-3+1=5, ok
  Back removal: nums[6]=6 <= 7 → pop 6
  Deque: [] → push 7
  Deque: [7]  (values: [7])
  result = [3, 3, 5, 5, 6, nums[7]=7]
 
FINAL: [3, 3, 5, 5, 6, 7] ✓
 
Time:  O(N)  — each index enters and leaves deque at most once
Space: O(k)  — deque holds at most k indices
*/

---

9. Self-Assessment Checklist

Checklist sau khi học Monotonic Stack & Queue

• Giải thích được tại sao monotonic stack là O(N) dù có nested while loop
• Biết khi nào dùng increasing vs decreasing stack
• Giải Daily Temperatures #739 không nhìn note (< 10 phút)
• Giải Largest Rectangle in Histogram #84 với sentinel trick
• Implement sliding window max với deque, giải thích từng bước
• Trapping Rain Water — giải được bằng stack approach
• Nhận ra “next greater element” pattern trong bài toán mới
• Giải thích khi nào store index vs value trong stack

Luyện tập tiếp theo

• #503 Next Greater Element II (circular array — dùng i % n trick)
• #901 Online Stock Span (stack stores (price, span) pairs)
• #402 Remove K Digits (greedy với increasing stack)
• #907 Sum of Subarray Minimums (monotonic stack + contribution)

---

Tags: dsa monotonic-stack monotonic-queue deque sliding-window faang-mastery Related: 02-Bit-Manipulation | 04-Advanced-Binary-Search | Pattern-Stack-Queue