[BOJ]6549 히스토그램에서 가장 큰 직사각형

• 풀지 못한 문제이다. 코딩테스트에서 나올 수 있는 최고난이도 수준의 스택 문제
• sol1: 이전 블록의 높이보다 작거나 같은 높이의 블록을 만날 때마다, 최대 넓이 계산
• 마지막에 스택에 남은 블록에 대해 넓이 계산
• 계산한 넓이 중 최 대값만을 기억해 출력

#include <bits/stdc++.h>
using namespace std;
#define H first
#define X second
int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    while (true) {
        // 입력: 히스토그램의 막대 개수 (n)
        int n;
        cin >> n;
        // n이 0이면 종료
        if (n == 0) break;
        // 스택 선언
        stack<pair<long long, long long>> S;
        // 최대 넓이
        long long ans = 0;
        // 각 막대 정보 순회
        for (int i = 0; i < n; i++) {
            // 막대 높이 입력
            int h;
            cin >> h;
            // 현재 막대 정보
            int idx = i;
            // 스택이 비어있지 않고, 현재 막대보다 높은 막대가 존재하는 경우
            while (!S.empty() && S.top().H >= h) {
                // 이전 막대로 만들 수 있는 최대 넓이 계산
                ans = max(ans, (i - S.top().X) * S.top().H);
                // 최대 넓이 계산에 사용된 막대 정보 제거
                idx = S.top().X;
                S.pop();
            }
            // 현재 막대 정보 스택에 추가
            S.push({h, idx});
        }
        // 남은 막대 정보 처리
        while (!S.empty()) {
            // 스택에 남은 막대로 만들 수 있는 최대 넓이 계산
            ans = max(ans, (n - S.top().X) * S.top().H);
            // 스택 비우기
            S.pop();
        }
        // 최대 넓이 출력
        cout << ans << '\n';
    }
}