Hình chữ nhật lớn nhất

Nguồn: CLUE OJ – Chương 15: Ngăn xếp, Hàng đợi Độ khó: Khá Ngăn xếp đơn điệu Histogram

Đề 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$.

Ví dụ – input

2
7
6 2 5 4 5 1 6
3
2 2 2

Ví dụ – output

12
6

Giả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ộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 test, 6 subtaskÝ tưởngL[i], R[i]Cách 1O(N³)Cách 2O(N²)Cách 3ngăn xếp O(N)

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ùng long 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)$.

Tìm L[i] bằng ngăn xếp đơn điệu

Duyệt $i$ từ trái sang phải, giữ một ngăn xếp các chỉ số có chiều cao tăng dần từ đáy lên đỉnh. Tới cột $i$: bỏ (pop) mọi cột ở đỉnh có chiều cao $\ge H[i]$ – chúng không bao giờ là "cột thấp hơn gần nhất" của ai ở bên phải nữa, vì cột $i$ vừa thấp hơn (hoặc bằng) vừa gần hơn. Sau khi bỏ, đỉnh ngăn xếp (nếu có) chính là $L[i]$. Rồi đẩy $i$ vào. Tìm $R[i]$ thì làm y hệt nhưng duyệt từ phải sang trái.

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):

Chiều cao các cột:

Ví dụ nhanh:

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.

C++▶ Chạy tay từng dòng codeCách 1: duyệt mọi đoạn [l, r], tìm cột thấp nhất bằng vòng lặp k – O(N³).

Dữ liệu vào (stdin) – sửa thoải mái2 7 6 2 5 4 5 1 6 3 2 2 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Biến mn và ans là long long để tích mn * (r - l + 1) không tràn số (với int thì test 51–100 sẽ sai).
2. 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ể).

Không gian$O(N)$

Thời gian$O(T \cdot N^3)$

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:

C++▶ Chạy tay từng dòng codeCách 2: cố định l, tăng dần r và cập nhật min – O(N²).

Dữ liệu vào (stdin) – sửa thoải mái2 7 6 2 5 4 5 1 6 3 2 2 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(N)$

Thời gian$O(T \cdot N^2)$

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.

C++▶ Chạy tay từng dòng codeCách 3: hai lần duyệt với ngăn xếp tìm L[i], R[i], rồi lấy max h[i]·(R[i] − L[i] − 1) – O(N).

Dữ liệu vào (stdin) – sửa thoải mái2 7 6 2 5 4 5 1 6 3 2 2 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. 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.
2. 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$.
3. 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ý.)
4. 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ũ.

Không gian$O(N)$

Thời gian$O(T \cdot N)$

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

Ghi chú của mình: thời gian trong bảng là thời gian CPU đo trên máy của mình (giới hạn 1 giây/test). Cách 3 với C++ chạy mọi test dưới 0,19 giây. Bản Python của Cách 3 đúng 90/100 test – quá 1 giây ở các test 91–100 (chủ yếu là các test $T = 20$, phải xử lý tới $2 \cdot 10^6$ cột): Python chậm hơn C++ nhiều lần, thuật toán vẫn đúng. Hai bài tiếp theo Hình chữ nhật 0 1 ver 1 / ver 2 sẽ dùng lại nguyên đoạn code ngăn xếp này cho từng hàng của bảng – các bạn nhớ kỹ nhé.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇