[문제풀이] 6549번: 히스토그램에서 가장 큰 직사각형

[문제풀이] 6549번: 히스토그램에서 가장 큰 직사각형

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

문제유형

스택

Solution

#include <stdio.h>
int N;
struct STACK
{
    int h, pos;
}stack[100000 + 10];
#define MAX(a,b) ((a)>(b)?(a):(b))
int input_data(void)
{
    scanf("%d", &N);
    if (N == 0)return 1;
    return 0;
}
long long solve(void)
{
    int sp = 0;
    long long max = 0, area;
    int i, h, pos;
 
    for (i = 1; i <= N; i++)
    {
        scanf("%d", &h);
        pos = i;
        while (sp > 0 && stack[sp].h >= h)
        {
            area = (long long)stack[sp].h * (i - stack[sp].pos);
            max = MAX(max, area);
            pos = stack[sp].pos;
            sp--;
        }
        stack[++sp].h = h;
        stack[sp].pos = pos;
    }
    for (; sp > 0; sp--)
    {
        area = (long long)stack[sp].h * (N + 1 - stack[sp].pos);
        max = MAX(max, area);
    }
    return max;
}
int main(void)
{
    long long sol;
    for (;;)
    {
        if (input_data())break;
        sol = solve();
        printf("%lld\n", sol);
    }
    return 0;
}