Largest Rectangle
http://poj.org/problem?id=2559
use a stack to store the rectangles (width, height)
the height is increasing
https://www.spoj.com/problems/HISTOGRA/
monotonic stack
from 1 to n
decreasing stack, stack used from 1
for (int i = 1; i <= n; i++)
{
while (ss > 0 && h[s[ss]] < h[i])
{
answer[s[ss--]] = i;
}
s[++ss] = i;
}
from n downto 1
decreasing stack, stack used from 1
for (int i = n; i > 0; i--) {
while (ss > 0 && h[s[ss]] <= h[i]) {
ss--;
}
z[i] = s[ss];
s[++ss] = i;
}
doubly linked list
to delete i
for (int i = 0; i < n; i++)
{
// do them in {p[i]} order
R[L[p[i]]] = R[p[i]]
L[R[p[i]]] = L[p[i]]
// R[p[i]] is the answer of p[i]
}