[BOJ] 히스토그램

[BOJ] 히스토그램

Problem URL : 히스토그램

#include<iostream>
#include<stack>
using namespace std;

int main() {
    int n, hList[100000];
    scanf("%d", &n);

    stack<int> s;
    long long maxArea = 0;
    long long area;
    
    s.push(0);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &hList[i]);
        while (s.size() > 1 && hList[s.top()] >= hList[i]) {
            int height = hList[s.top()];
            s.pop();
            // height 로 만들 수 있는 최대 사각형 넓이
            area = (i - 1 - s.top()) * height;
            maxArea = maxArea < area ? area : maxArea;
        }
        s.push(i);
    }

    while (s.size() > 1) {
        //남은 stack의 원소들이 오름차순이기에
        //그래프 끝까지가 사각형 밑변의 길이가 된다.
        int height = hList[s.top()];
        s.pop();
        area = (n  - s.top()) * height;
        maxArea = maxArea < area ? area : maxArea;
    }
    printf("%lld\n", maxArea);
}