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

[문제]
https://www.acmicpc.net/problem/6549

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

[풀이]
1. 스택을 이용한 방법
최대 넓이를 구하기 위해서 스택의 top에 존재하는 높이 값이 현재 높이값보다 크거나 같을때까지 스택을 탐색하여 최대 넓이를 구한다.
스택에는 (삭제할때의 idx, 높이)를 저장하고, 스택에 저장하면 된다.
주의할 점은 0~n 까지 탐색할 경우 마지막에 넣은 높이의 넓이를 구할수 없으므로, S.empty()를 조사하여 최대 넓이를 구하도록 한다.

[코드]

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    while(1){
        int n;
        cin >> n;
        if(n == 0) break;
        long long ans = 0LL;
        stack<pair<int,int>> S;
        for(int i=0; i<n; i++){
            int h;
            int idx = i;
            cin >> h;
            while(!S.empty() && S.top().second >= h){
                ans = max(ans, 1LL * (i-S.top().first) * S.top().second);
                idx = S.top().first;
                S.pop();
            }
            S.push({idx, h});
    
        }
        while(!S.empty()){
            ans = max(ans, 1LL*(n-S.top().first)*S.top().second);
            S.pop();
        }
        cout << ans << "\n";
    }
}