6549번: 히스토그램에서 가장 큰 직사각형

https://www.acmicpc.net/problem/6549


$O(tn)$

각 막대마다 자신을 시작으로 하는 최대 직사각형을 찾을 수 있는데 이러한 n개의 부분해들 중 최대값이 전체 문제의 해가 될 것이다.
이러한 최대 직사각형은 monotonous stack(이하 스택)를 이용하여 각각 amortized O(1)에 구할 수 있다.

막대를 입력받을 때마다 스택에 (x위치, 높이) 정보를 저장한다.
스택의 최근에 저장한 막대의 높이가 새로 입력받는 막대의 높이보다 작거나 같을 때까지 스택에서 pop을 하며 해당 막대를 시작으로 하는 최대 직사각형의 넓이를 구해준다.
이때 스택에는 막대들 높이가 오름차순으로 유지되므로 최대 직사각형의 밑변 길이는 해당 막대와 새로 추가하고자 하는 막대의 x좌표 차이가 될 것이다.
처음과 끝에 높이가 0인 더미 막대를 추가해주면 쉽게 구현할 수 있다.

#include<cstdio>
#define max(x,y) x>y?x:y
const int MXN = 1e5;
int n, a[MXN + 2], stk[MXN + 1], top;
long long r;
void push(int h) {
    while (a[stk[top - 1]] > a[h]) --top, r = max(r, (long long)a[stk[top]] * (h - 1 - stk[top - 1]));
    stk[top++] = h;
}
int main() {
    while (scanf("%d", &n) && n) {
        top = 1; r = a[n + 1] = 0;
        for (int i = 1; i <= n; i++) scanf("%d", a + i), push(i);
        push(n + 1);
        printf("%lld\n", r);
    }
    return 0;
}