Tìm hình chữ nhật lớn nhất trên SPOJ

[ntmtmn (Nguyen Tuan)]

Bài này giải làm sao để không bị time limit a:

SSAM219G - HÌNH CHỮ NHẬT LỚN NHẤT

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 ≤ 20).
Mỗi test bắt đầu bởi số nguyên N (N ≤ 100 000).
Dòng tiếp theo gồm N số nguyên H[i] (1 ≤ H[i] ≤ 109).

Output:
Với mỗi test, in ra diện tích hình chữ nhật lớn nhất tìm được.

Ví dụ:
Input

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

Output

12
6

Link: https://www.spoj.com/PTIT/problems/SSAM219G/

[tcm (Người bí ẩn)]

Bài này bạn dùng deque (hoặc list cũng được nhưng chậm hơn), dùng thuật toán left-right.
https://blog.hiepho.tech/2014/03/thuat-toan-left-right.html
Đầu tiên bạn nghĩ thuật trâu trước như sau: Duyệt cố định cột thứ i, sau đó loang sang bên trái và bên phải tới khi gặp cột có chiều cao nhỏ hơn cột i. Diện tích sẽ bằng độ phủ chiều ngang x chiều cao cột i. ĐPT là O(n^2).
Nhận thấy rằng việc loang tìm cột có chiều cao <= chiều cao cột i và cột i + 1 là 2 bài toán giao nhau, thuật O(n^2) sẽ không tối ưu. Và trên thực tế, giả sử loang bên trái, nếu mình tìm được cột j đầu tiên sao cho j < i và H[j] < H[i] thì các cột từ j + 1 đến i - 1 là vô nghĩa, không cần xét. Đây là tư tưởng cho việc áp dụng stack để đạt thuật O(n).
Mở rộng là bài toán tìm min/max trên đoạn tịnh tiến dùng deque mà VNOI đã có bài hướng dẫn: https://vnoi.info/wiki/algo/data-structures/deque-min-max