Largest Rectangle in Histogram

Độ Khó: Hard

Bài toán

Cho một mảng các số nguyên heights biểu diễn chiều cao các cột của biểu đồ (histogram). Độ rộng mỗi cột là 1. Tìm diện tích hình chữ nhật lớn nhất có thể vẽ được trong biểu đồ này.

Ví dụ:

Input: heights = [2,1,5,6,2,3]
Output: 10
Giải thích: Hình chữ nhật lớn nhất được tạo bởi cột 5 và 6 (độ cao min là 5, độ rộng 2). Diện tích 5 * 2 = 10.

Phân Tích & Tiếp Cận

Cách 1: Brute Force

Với mỗi cột i, lan sang trái và phải xem có thể mở rộng đến đâu (cho đến khi gặp cột thấp hơn heights[i]).

• Time: $O(n^2)$.

Cách 2: Monotonic Increasing Stack

Ý tưởng: Với một cột có chiều cao H, diện tích lớn nhất nó có thể đóng góp là H * Width. Width được tính từ điểm đầu tiên bên trái thấp hơn nó (left boundary) tới điểm đầu tiên bên phải thấp hơn nó (right boundary).

Ta dùng Stack tăng dần (Monotonic Increasing Stack).

1. Khi gặp một cột cao hơn đỉnh stack: Nó có tiềm năng mở rộng sang phải. Push vào.
2. Khi gặp một cột thấp hơn (hoặc bằng):
   • Điều này có nghĩa là các cột cao hơn trong Stack đã bị chặn đứng ở bên phải. Chúng không thể mở rộng thêm nữa.
   • Ta phải tính toán ngay diện tích của các cột bị chặn này (Pop chúng ra).
   • Chiều cao H = Chiều cao cột vừa pop.
   • Chiều rộng W = (index hiện tại) - (index cột vừa lộ ra ở đỉnh stack mới) - 1.

function largestRectangleArea(heights: number[]): number {
    const stack: number[] = []; // Lưu index
    let maxArea = 0;
    
    // Thêm số 0 vào cuối mảng để ép tất cả phần tử còn sót lại trong stack phải pop ra ở bước cuối
    const h = [...heights, 0];

    for (let i = 0; i < h.length; i++) {
        // Khi gặp cột thấp hơn đỉnh stack -> Pop và tính toán
        while (stack.length > 0 && h[i] < h[stack[stack.length - 1]]) {
            const height = h[stack.pop()!];
            
            // Nếu stack rỗng, nghĩa là height này bé nhất từ đầu mảng tới giờ
            // Chiều rộng = i
            // Nếu stack còn, chiều rộng = i - (index phần tử kế tiếp) - 1
            const width = stack.length === 0 ? i : i - stack[stack.length - 1] - 1;
            
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    
    return maxArea;
}

• Time Complexity: $O(n)$ - Mỗi cột push/pop 1 lần.
• Space Complexity: $O(n)$.

Trick quan trọng

Việc thêm 0 vào cuối mảng ([...heights, 0]) là một kỹ thuật cực hay để tránh phải viết thêm một vòng lặp while riêng lẻ sau khi kết thúc vòng for. Nó hoạt động như một "Sentinel Value" (Lính canh) để dọn dẹp Stack.