Tutorial — Cột trụ

Thay vì duyệt qua từng kích thước nhóm rồi tìm nhóm có giá trị nhỏ nhất lớn nhất, hãy đổi góc nhìn bằng cách xét xem mỗi cột trụ $i$ có thể là cột trụ thấp nhất của những nhóm cột nào.

Với mỗi vị trí $i$, hãy tìm vị trí $left_i$ gần nhất bên trái và $right_i$ gần nhất bên phải có độ cao nhỏ hơn $a_i$. Khi đó cột trụ $i$ là phần tử nhỏ nhất trong đoạn có độ dài tối đa là $len_i = right_i - left_i - 1$, nghĩa là giá trị $a_i$ là ứng viên cho độ chịu lực của nhóm có kích thước $len_i$ cũng như mọi kích thước nhỏ hơn.

Sử dụng ngăn xếp đơn điệu (monotonic stack) để tính nhanh mảng $left$ và $right$ trong thời gian $O(n)$, sau đó ghi nhận $ans[len_i] = \max(ans[len_i], a_i)$ cho từng $i$. Cuối cùng, cập nhật mảng kết quả bằng cách duyệt lùi từ $n - 1$ về $1$ với công thức $ans[x] = \max(ans[x], ans[x + 1])$.