Largest Rectangle in Histogram: monotonic stack như một chiếc oracle tìm biên

Chọn bất kỳ thanh nào tại index i. Nếu muốn vẽ hình chữ nhật cao nhất có thể dùng toàn bộ chiều cao của thanh đó, bạn cần biết có thể mở rộng sang trái và sang phải bao xa trước khi gặp thanh thấp hơn. Ngay khi gặp thanh ngắn hơn heights[i], thanh đó không thể là một phần của hình chữ nhật có chiều cao heights[i] — bạn dừng lại. Chiều rộng của hình chữ nhật được xác định bởi hai biên đó. Diện tích là heights[i] * width.

Cách đặt vấn đề này biến "hình chữ nhật lớn nhất" thành "với mỗi thanh, tìm biên trái và biên phải là thanh thấp hơn đầu tiên." Phần còn lại chỉ là chọn cách tìm biên đó hiệu quả như thế nào.

Constraints đẩy mạnh về hiệu quả. 1 <= heights.length <= 10^5 và 0 <= heights[i] <= 10^4. Một trăm nghìn thanh. Nếu tìm biên mất O(n) cho mỗi thanh, tổng cộng là O(n²) — khoảng 10^10 phép toán trong trường hợp xấu nhất, chắc chắn sẽ time out. Constraints đang nói với bạn rằng O(n) hoặc tệ lắm O(n log n) là bắt buộc. Đó không phải gợi ý — đó là chỉ thị.

Đề bài

Cho một mảng số nguyên heights trong đó mỗi phần tử là chiều cao của một thanh histogram có chiều rộng bằng 1, hãy trả về diện tích hình chữ nhật lớn nhất có thể tạo thành trong histogram đó. Đề gốc: LeetCode 84.

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

Brute force: quét biên cho từng thanh

Brute force rất trực tiếp. Với mỗi thanh i, đi sang trái cho đến khi tìm thanh ngắn hơn heights[i], đi sang phải tương tự, tính diện tích, theo dõi giá trị lớn nhất.

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        n = len(heights)
        max_area = 0
 
        for i in range(n):
            # Đi sang trái tìm thanh đầu tiên ngắn hơn heights[i]
            left = i
            while left > 0 and heights[left - 1] >= heights[i]:
                left -= 1
 
            # Đi sang phải tìm thanh đầu tiên ngắn hơn heights[i]
            right = i
            while right < n - 1 and heights[right + 1] >= heights[i]:
                right += 1
 
            width = right - left + 1
            max_area = max(max_area, heights[i] * width)
 
        return max_area

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        int n = heights.Length;
        int maxArea = 0;
 
        for (int i = 0; i < n; i++) {
            int left = i;
            while (left > 0 && heights[left - 1] >= heights[i])
                left--;
 
            int right = i;
            while (right < n - 1 && heights[right + 1] >= heights[i])
                right++;
 
            int width = right - left + 1;
            maxArea = Math.Max(maxArea, heights[i] * width);
        }
 
        return maxArea;
    }
}

Cách này đúng. Với input giảm dần như [5, 4, 3, 2, 1], thanh 0 (chiều cao 5) đi sang phải bốn bước, thanh 1 đi ba bước, v.v. — tổng số bước là n + (n-1) + ... + 1 = O(n²). Các vòng lặp bên trong không phải hằng số; chúng tỉ lệ thuận với khoảng cách đến biên.

Time: O(n²). Space: O(1). Đúng với input nhỏ, sẽ không qua với n = 10^5.

Monotonic stack: O(n) khi mỗi thanh chỉ vào và ra một lần

Vấn đề cốt lõi: brute force tính lại biên từ đầu cho mỗi thanh. Sự dư thừa rất lớn — khi thanh i đi sang trái và tìm biên, nó thường đang làm lại công việc thanh i-1 đã làm.

Monotonic stack loại bỏ điều này bằng cách xử lý biên một cách lười biếng. Thay vì tìm biên phải của thanh khi thăm nó, bạn khám phá biên đó sau — khi một thanh ngắn hơn xuất hiện và thông báo với tất cả thanh cao hơn đứng sau nó: "vương quốc của các bạn đã kết thúc."

Đây là invariant: stack luôn chứa các index theo thứ tự chiều cao tăng dần (từ dưới lên trên). Khi thanh i xuất hiện:

• Nếu heights[i] cao ít nhất bằng đỉnh stack, nó kéo dài biên phải hiện có, push i vào stack.
• Nếu heights[i] thấp hơn, nó là biên phải của mọi thanh cao hơn ở đỉnh stack. Pop từng thanh đó, tính diện tích với i là giới hạn phải, rồi push i.

Sau vòng lặp chính, các thanh còn trong stack có thể mở rộng đến cạnh phải của mảng — xử lý chúng với n là giới hạn phải.

class Solution:
    def largestRectangleArea(self, heights: list[int]) -> int:
        stack = []   # các index, duy trì theo thứ tự chiều cao tăng dần
        max_area = 0
        n = len(heights)
 
        for i in range(n):
            while stack and heights[i] < heights[stack[-1]]:
                height = heights[stack.pop()]
                # Biên trái: đỉnh stack mới (exclusive), hoặc index 0 nếu stack rỗng
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)
 
        # Các thanh còn lại có thể mở rộng đến cạnh phải
        while stack:
            height = heights[stack.pop()]
            width = n if not stack else n - stack[-1] - 1
            max_area = max(max_area, height * width)
 
        return max_area

public class Solution {
    public int LargestRectangleArea(int[] heights) {
        var stack = new Stack<int>();
        int maxArea = 0;
        int n = heights.Length;
 
        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && heights[i] < heights[stack.Peek()]) {
                int height = heights[stack.Pop()];
                int width = stack.Count == 0 ? i : i - stack.Peek() - 1;
                maxArea = Math.Max(maxArea, height * width);
            }
            stack.Push(i);
        }
 
        while (stack.Count > 0) {
            int height = heights[stack.Pop()];
            int width = stack.Count == 0 ? n : n - stack.Peek() - 1;
            maxArea = Math.Max(maxArea, height * width);
        }
 
        return maxArea;
    }
}

Công thức tính width cần đọc kỹ. Khi bạn pop thanh j:

• Biên phải của nó là i (thanh kích hoạt pop), exclusive.
• Biên trái là stack[-1] + 1 sau khi pop (đỉnh mới), exclusive. Nếu stack rỗng sau khi pop, không có gì ngắn hơn ở bên trái j, nên biên trái là index 0 — và width = i - 0 = i.

Tóm lại: width = i - stack[-1] - 1 khi stack không rỗng, và width = i khi stack rỗng.

Trace từng bước: heights = [2, 1, 5, 6, 2, 3]

i=0, h=2:  stack=[], push 0        -> stack=[0]
i=1, h=1:  h < heights[0]=2, pop 0
             height=2, stack=[], width=1, area=2*1=2
           push 1                  -> stack=[1]
i=2, h=5:  h > heights[1]=1, push 2 -> stack=[1,2]
i=3, h=6:  h > heights[2]=5, push 3 -> stack=[1,2,3]
i=4, h=2:  h < heights[3]=6, pop 3
             height=6, stack=[1,2], width=4-2-1=1, area=6*1=6
           h < heights[2]=5, pop 2
             height=5, stack=[1], width=4-1-1=2, area=5*2=10  <-- max hiện tại
           h >= heights[1]=1, push 4 -> stack=[1,4]
i=5, h=3:  h > heights[4]=2, push 5 -> stack=[1,4,5]

Dọn stack:
  pop 5: height=3, stack=[1,4], width=6-4-1=1, area=3*1=3
  pop 4: height=2, stack=[1],   width=6-1-1=4, area=2*4=8
  pop 1: height=1, stack=[],    width=6,        area=1*6=6

max_area = 10

Hình chữ nhật diện tích 10 được tạo bởi các thanh tại index 2 và 3 (chiều cao 5 và 6), dùng chiều cao 5 (giá trị tối thiểu). Chiều rộng = 2. Đó là kết quả.

Lưu ý thanh 1 (chiều cao 1) ở lại trong stack suốt vòng lặp chính — nó là minimum toàn cục nên không bị pop cho đến giai đoạn dọn stack, và khi đó nó trải dài toàn bộ mảng (width 6, area 6).

Tại sao lại O(n)?

Mỗi index thanh vào stack đúng một lần (qua stack.append) và ra đúng một lần (qua stack.pop). Tổng số thao tác push + pop xuyên suốt thuật toán là đúng 2n. Vòng while bên trong vòng for trông có vẻ thêm một nhân tố, nhưng mỗi lần lặp của while đó là một lần pop — và có tối đa n lần pop tổng cộng. Vì vậy vòng chính là O(n), vòng dọn stack là O(n), tổng là O(n). Stack dùng O(n) space trong trường hợp xấu nhất (input tăng dần như [1, 2, 3, 4, 5], khi không có gì được pop cho đến khi dọn stack).

Các edge case thực sự gây nhầm lẫn

Một thanh (heights = [5]): i=0 push 5; vòng chính kết thúc; dọn stack pop nó với stack=[], nên width = n = 1, area = 5. Đúng.

Tăng dần nghiêm ngặt ([1, 2, 3, 4]): không có gì pop trong vòng chính — invariant monotonic không bao giờ bị vi phạm. Cả bốn thanh vào stack. Dọn stack xử lý từ phải sang trái: thanh 3 có width 1, thanh 2 có width 2, thanh 1 có width 3, thanh 0 có width 4. Lớn nhất là 1*4 = 4. Đúng — và đây cũng là trường hợp xấu nhất cho kích thước stack.

Giảm dần nghiêm ngặt ([4, 3, 2, 1]): mỗi thanh mới kích hoạt một lần pop. Thanh 0 (height 4) được push, rồi pop ngay khi thanh 1 (height 3) đến: width = 1, area = 4. Thanh 1 được push, pop tại thanh 2: width = 2, area = 6. Thanh 2 pop tại thanh 3: width = 3, area = 6. Thanh 3 còn lại, dọn stack: width = 4, area = 4. Lớn nhất là 6.

Tất cả cùng chiều cao ([3, 3, 3]): các chiều cao bằng nhau, nên heights[i] < heights[stack[-1]] là false — không pop trong vòng chính. Cả ba push vào. Dọn stack: thanh 2 có width 1, thanh 1 có width 2, thanh 0 có width 3. Lớn nhất là 3*3 = 9.

Thanh chiều cao 0 ([2, 0, 2]): thanh 1 (height 0) kích hoạt pop tất cả những gì cao hơn. Thanh 0 (height 2) bị pop: stack=[], nên width = 1, area = 2. Sau đó thanh 1 (height 0) được push. Thanh 2 (height 2) đến — không pop. Dọn stack pop thanh 2: stack=[1], width = 3-1-1 = 1, area = 2. Rồi thanh 1: stack=[], width = 3, area = 0. Lớn nhất là 2. Thanh chiều cao 0 thực chất là một bức tường ngăn cách mọi thứ. Code xử lý nó một cách tự nhiên — area = 0 * bất kỳ = 0.

Vấn đề overflow: heights[i] <= 10^4 và heights.length <= 10^5, nên diện tích tối đa là 10^4 * 10^5 = 10^9. Giá trị này vừa trong 32-bit signed integer (tối đa khoảng 2.1 * 10^9). Trong C# dùng int không lo ngại; trong Python số nguyên có độ chính xác tùy ý.

Bảng so sánh

Ưu thế O(1) space của brute force là có thật nhưng không liên quan trong thực tế. Với n = 10^5 nó sẽ time out. O(n) space của stack là không thể tránh khỏi — trong trường hợp xấu nhất (input tăng dần), mọi thanh đều đồng thời trong stack.

Mental model: stack như một boundary oracle

Pattern ở đây là "next smaller element" — với mỗi phần tử, tìm phần tử đầu tiên bên phải (hoặc trái) nhỏ hơn nghiêm ngặt. Đây là ứng dụng canonical của monotonic stack. Stack đóng vai trò bộ nhớ của "các thanh chưa tìm được biên phải." Khi thanh i xuất hiện ngắn hơn đỉnh stack, nó trở thành biên phải của tất cả những gì nó vừa pop.

Cùng pattern oracle này xuất hiện ở:

• Trapping Rain Water (42): thay vì "thanh này có thể mở rộng rộng bao nhiêu," bạn hỏi "bao nhiêu nước đọng trên thanh này." Monotonic stack tương tự, nhưng tính thể tích bị giữ lại thay vì diện tích hình chữ nhật. Cấu trúc pop-and-compute gần như giống hệt.
• Daily Temperatures (739): tìm ngày ấm hơn tiếp theo cho mỗi ngày. Next-greater-element dạng thuần túy. Stack giữ "những ngày đang chờ câu trả lời ấm hơn"; mỗi ngày ấm mới pop và giải quyết các entries đang chờ.
• Next Greater Element I và II (496, 503): dạng thô của pattern, không có tính toán diện tích. 496 là bài khởi động tốt nếu bài này còn quá dày đặc; 503 thêm biến thể mảng vòng.
• Maximal Rectangle (85): mở rộng bài này lên ma trận 2D. Xây dựng histogram cho mỗi hàng (chiều cao mỗi ô là số 1 liên tiếp phía trên trong cùng cột), rồi chạy đúng thuật toán này trên histogram của mỗi hàng. Cùng code, thêm một cấp độ lồng nhau.

Vị trí trong stack series và cách trình bày trong phỏng vấn

Đây là bài stack khó nhất trong series. Valid Parentheses dạy nhịp push-and-pop cơ bản; Evaluate Reverse Polish Notation dạy stack như thiết bị tính toán; Min Stack thêm auxiliary tracking. Largest Rectangle in Histogram là bài đầu tiên mà nội dung của stack thay đổi theo cách không hiển nhiên — bạn đang duy trì một structural invariant (thứ tự monotonic) và dùng vi phạm invariant đó như trigger để tính toán kết quả.

Điều tôi sẽ làm trong phỏng vấn thực tế: bắt đầu bằng cách nói rõ framing "mỗi thanh là chiều cao tối thiểu," phác thảo brute force trong hai phút, nêu rõ O(n²), rồi nói "sự dư thừa là chúng ta tính lại biên mà chúng ta đã biết." Chuyển tiếp đó giúp bạn vào phần monotonic stack. Implement giải pháp stack, trace qua ví dụ [2, 1, 5, 6, 2, 3], và chỉ ra rằng công thức width là điểm duy nhất cần cẩn thận (stack rỗng -> width = i hoặc n).

Trong production tôi sẽ dùng monotonic stack ngay lập tức. Brute force O(n²) không bao giờ đúng với n = 10^5. Stack thêm O(n) memory nhưng cải tiến từ bậc hai xuống tuyến tính là không thể thương lượng ở quy mô đó. Code khoảng 15 dòng trong cả hai ngôn ngữ, và invariant (các index theo thứ tự chiều cao tăng dần) dễ phát biểu và kiểm tra.