Hình chữ nhật lớn nhất
Đề bài
Cho $N$ cột, mỗi cột có chiều cao bằng $H[i]$. Bạn hãy tìm hình chữ nhật lớn nhất bị che phủ bởi các cột?
Input:
- Dòng đầu tiên là số lượng bộ test $T$ $(T \le 20)$.
- Mỗi test bắt đầu bởi số nguyên $N$ $(N \le 100\,000)$.
- Dòng tiếp theo gồm $N$ số nguyên $H[i]$ $(1 \le H[i] \le 10^9)$.
Output: với mỗi test, in ra diện tích hình chữ nhật lớn nhất tìm được.
Subtask:
- $20\%$ số test đầu tiên có $T = 1,\ N \le 20$;
- $10\%$ số test tiếp theo có $T = 1,\ N \le 10^2$;
- $10\%$ số test tiếp theo có $T = 1,\ N \le 10^3$;
- $10\%$ số test tiếp theo có $T = 1,\ N \le 10^4$;
- $40\%$ số test tiếp theo có $T = 1,\ N \le 10^5$;
- $10\%$ số test còn lại có $T = 20,\ N \le 10^5$.
2
7
6 2 5 4 5 1 6
3
2 2 212
6Giải thích ví dụ: test 1 là đúng hình trên – 3 cột liền nhau cao $5, 4, 5$ chứa được hình chữ nhật cao $4$, rộng $3$, diện tích $12$. Test 2 có 3 cột cùng cao $2$ → hình chữ nhật $2 \times 3 = 6$.
Lời mở đầu
Đây là bài toán "Largest Rectangle in Histogram" nổi tiếng – một trong những ứng dụng đẹp nhất của ngăn xếp đơn điệu (monotonic stack). Bài này còn là "viên gạch" cho hai bài tiếp theo trong chương: Hình chữ nhật 0 1 ver 1 và ver 2 (tìm hình chữ nhật toàn số 0 lớn nhất trong bảng). Mình sẽ đi từ cách vét cạn $O(N^3)$, qua $O(N^2)$, rồi tới cách dùng ngăn xếp $O(N)$, kèm kết quả chạy thật trên bộ test của CLUE.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
| Test | T | N | H[i] | Dạng dữ liệu | Đáp án lớn nhất |
|---|---|---|---|---|---|
| 1 – 20 | 1 | 3 … 18 | 1 … 20 | ngẫu nhiên | 91 |
| 21 – 30 | 1 | 100 | 34 … 32.749 | ngẫu nhiên | 194.000 |
| 31 – 40 | 1 | 1.000 | 5 … 32.756 | ngẫu nhiên | 279.279 |
| 41 – 50 | 1 | 10.000 | 1 … 32.768 | ngẫu nhiên | 375.870 |
| 51 – 70 | 1 | 100.000 | 1 … 100.000 | tăng dần $1, 2, \ldots, 10^5$ (20 test giống hệt nhau) | 2.500.050.000 |
| 71 – 90 | 1 | 100.000 | 1 … 100.000 | giảm dần $10^5, \ldots, 2, 1$ (20 test giống hệt nhau) | 2.500.050.000 |
| 91 – 95 | 20 | 100.000 | 1 … 50.001 | hình "kim tự tháp" $1, 2, \ldots, 50001, \ldots, 2, 1$ (5 test giống nhau) | 1.250.050.000 |
| 96 – 100 | 20 | 100.000 | 1 … 32.768 | ngẫu nhiên | 541.972 |
- Bộ test có 100 test, chia đúng theo 6 subtask của đề.
- Subtask 5 thật ra chỉ có 2 bộ dữ liệu: test 51–70 giống hệt nhau (dãy tăng $1, 2, \ldots, 10^5$), test 71–90 giống hệt nhau (dãy giảm). Test 91–95 cũng giống nhau (20 dãy "kim tự tháp"). Chiều cao lớn nhất thực tế chỉ là $10^5$ (test 21–50 và 96–100 có $H[i] \le 32768$ – có lẽ sinh bằng
rand()). - Bẫy tràn số: đáp án lớn nhất là $2{.}500{.}050{.}000$ (với dãy $1, 2, \ldots, 10^5$: hình cao $50001$ rộng $50000$) – vượt quá giới hạn của
int($\approx 2{,}1 \cdot 10^9$). Theo đề thì $H[i]$ tới $10^9$, $N$ tới $10^5$ nên đáp án có thể tới $10^{14}$. Phải dùnglong long!
Các subtask khớp với bộ test như sau (ô ghi số test đúng của từng cách C++ – chạy thật):
| Subtask | Điều kiện | Các test | Cách 1 $O(N^3)$ | Cách 2 $O(N^2)$ | Cách 3 ngăn xếp $O(N)$ |
|---|---|---|---|---|---|
| 1 (20%) | $T = 1,\ N \le 20$ | 1 – 20 | 20/20 | 20/20 | 20/20 |
| 2 (10%) | $T = 1,\ N \le 10^2$ | 21 – 30 | 10/10 | 10/10 | 10/10 |
| 3 (10%) | $T = 1,\ N \le 10^3$ | 31 – 40 | 10/10 | 10/10 | 10/10 |
| 4 (10%) | $T = 1,\ N \le 10^4$ | 41 – 50 | 0/10 | 10/10 | 10/10 |
| 5 (40%) | $T = 1,\ N \le 10^5$ | 51 – 90 | 0/40 | 0/40 | 40/40 |
| 6 (10%) | $T = 20,\ N \le 10^5$ | 91 – 100 | 0/10 | 0/10 | 10/10 |
Ý tưởngMỗi cột "làm chủ" một hình chữ nhật
Nhận xét 1. Một hình chữ nhật nằm trong các cột $l, l+1, \ldots, r$ thì chiều cao của nó không vượt quá cột thấp nhất trong đoạn đó. Vậy với đoạn $[l, r]$, hình chữ nhật tốt nhất có diện tích
$\min(H[l..r]) \times (r - l + 1)$
và đáp án là giá trị lớn nhất của biểu thức này trên mọi đoạn $[l, r]$. Đây chính là Cách 1 và Cách 2.
Nhận xét 2 (đổi góc nhìn). Thay vì chọn đoạn rồi tìm cột thấp nhất, ta chọn trước cột thấp nhất $i$: hình chữ nhật có chiều cao đúng bằng $H[i]$ và kéo dài sang trái, sang phải đến khi gặp cột thấp hơn $H[i]$ thì dừng. Gọi
- $L[i]$ = vị trí cột gần nhất bên trái $i$ có chiều cao $< H[i]$ (không có thì $L[i] = 0$);
- $R[i]$ = vị trí cột gần nhất bên phải $i$ có chiều cao $< H[i]$ (không có thì $R[i] = N + 1$).
Thì hình chữ nhật của cột $i$ nằm trong các cột $L[i] + 1 \ldots R[i] - 1$, diện tích $H[i] \times (R[i] - L[i] - 1)$. Hình chữ nhật lớn nhất chắc chắn là hình của một cột nào đó (chính là cột thấp nhất của nó), nên đáp án là $\max_i H[i] \times (R[i] - L[i] - 1)$.
Mỗi chỉ số được đẩy vào 1 lần và bị bỏ ra nhiều nhất 1 lần, nên cả quá trình chỉ tốn $O(N)$ dù có vòng while bên trong.
Em nhập dãy chiều cao rồi bấm Tiếp để xem ngăn xếp tìm $L$, tìm $R$, rồi tính hình chữ nhật của từng cột (cột vàng: đang xét, xanh: đang nằm trong ngăn xếp, đỏ: vừa bị bỏ ra):
Cách 1Vét mọi đoạn – O(N³)
Cài đặt thẳng Nhận xét 1: duyệt mọi cặp $(l, r)$, dùng thêm một vòng lặp tìm cột thấp nhất trong đoạn.
- Biến
mnvàanslàlong longđể tíchmn * (r - l + 1)không tràn số (vớiintthì test 51–100 sẽ sai). - Có khoảng $N^2/2$ đoạn, mỗi đoạn tốn tới $N$ bước tìm min → khoảng $N^3/6$ phép tính: với $N = 10^3$ là $1{,}7 \cdot 10^8$ (vẫn kịp), với $N = 10^4$ là $1{,}7 \cdot 10^{11}$ (không thể).
Kết quả chạy thật: bản C++ đúng 40/100 test (quá 1 giây ở các test 41–100), test đúng chạy lâu nhất 0.126s; bản Python đúng 30/100 test (quá thời gian ở các test 31–100), lâu nhất 0.02s.
Cách 2Giữ min khi mở rộng đoạn – O(N²)
Với $l$ cố định, khi tăng $r$ thêm 1 thì $\min(H[l..r])$ $= \min(\min(H[l..r-1]), H[r])$ – không cần tìm lại từ đầu. Bỏ được vòng lặp trong cùng:
Kết quả chạy thật: bản C++ đúng 50/100 test (quá 1 giây ở các test 51–100), test đúng chạy lâu nhất 0.059s; bản Python đúng 40/100 test (quá thời gian ở các test 41–100), lâu nhất 0.07s.
$N = 10^4$ thì $N^2/2 = 5 \cdot 10^7$ phép tính – C++ chạy thoải mái; nhưng $N = 10^5$ thì $5 \cdot 10^9$ – quá thời gian. Cần một ý tưởng tốt hơn hẳn.
Cách 3Ngăn xếp đơn điệu – O(N)
Cài đặt Nhận xét 2: hai lần duyệt với ngăn xếp để có mảng L, R, rồi một vòng lấy max. Mình đánh chỉ số từ 1 để $L[i] = 0$ và $R[i] = N + 1$ đóng vai "cột ảo cao 0" ở hai đầu.
while(!st.empty() && h[st.top()] >= h[i]) st.pop();– bỏ hết các cột không thấp hơn cột $i$. Sau vòng này ngăn xếp vẫn tăng dần (từ đáy lên đỉnh), và đỉnh là cột thấp hơn gần nhất.- Trước lần duyệt thứ hai phải làm rỗng ngăn xếp (
while(!st.empty()) st.pop();), nếu không thì các chỉ số còn sót từ lần duyệt trái sẽ làm sai $R$. - Với cột cao bằng nhau (ví dụ test 2:
2 2 2), cả ba cột đều cho cùng hình $2 \times 3$ – không sao, vì ta chỉ cần giá trị lớn nhất. (Ở bài ver 2 phải đếm số hình thì chuyện "trùng" này mới cần xử lý.) - Mảng/ngăn xếp được tạo lại trong mỗi test (khai báo bên trong
while(t--)) nên không cần xoá dữ liệu cũ.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.188s; bản Python đúng 90/100 test (quá thời gian ở các test 91–100), lâu nhất 0.10s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất (test đúng) | Ghi chú |
|---|---|---|---|---|
| 1. Vét mọi đoạn – $O(N^3)$ | C++ | 40/100 | 0.126s | Quá thời gian ở test 41–100 |
| Python | 30/100 | 0.024s | Quá thời gian ở test 31–100 | |
| 2. Giữ min khi mở rộng – $O(N^2)$ | C++ | 50/100 | 0.059s | Quá thời gian ở test 51–100 |
| Python | 40/100 | 0.073s | Quá thời gian ở test 41–100 | |
| 3. Ngăn xếp đơn điệu – $O(N)$ | C++ | 100/100 | 0.188s | Full điểm |
| Python | 90/100 | 0.105s | Quá thời gian ở test 91–100 |
Bản Python cho từng subtask:
| Subtask | Điều kiện | Các test | Cách 1 (Python) | Cách 2 (Python) | Cách 3 (Python) |
|---|---|---|---|---|---|
| 1 (20%) | $T = 1,\ N \le 20$ | 1 – 20 | 20/20 | 20/20 | 20/20 |
| 2 (10%) | $T = 1,\ N \le 10^2$ | 21 – 30 | 10/10 | 10/10 | 10/10 |
| 3 (10%) | $T = 1,\ N \le 10^3$ | 31 – 40 | 0/10 | 10/10 | 10/10 |
| 4 (10%) | $T = 1,\ N \le 10^4$ | 41 – 50 | 0/10 | 0/10 | 10/10 |
| 5 (40%) | $T = 1,\ N \le 10^5$ | 51 – 90 | 0/40 | 0/40 | 40/40 |
| 6 (10%) | $T = 20,\ N \le 10^5$ | 91 – 100 | 0/10 | 0/10 | 0/10 |
Nhận xét
Đăng nhận xét