백준 6549 히스토그램에서 가장 큰 직사각형 풀이 c++

[문제 링크]

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

[입출력 예]

입력	출력
7 2 1 4 5 1 3 3 4 1000 1000 1000 0	8 4000

[소스코드]

// Authored by : haneulkimdev
// Co-authored by : BaaaaaaaaaaarkingDog
// http://boj.kr/d98aedfde0e444509de83f1a21c8ef7e
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  while (true) {
    int n;
    cin >> n;
    if (n == 0) break;
    stack<pair<int, int>> S;
    long long ans = 0;
    for (int i = 0; i < n; i++) {
      int h;
      cin >> h;
      int idx = i;
      while (!S.empty() && S.top().X >= h) {//스택이 비거나 h보다 더 낮은 top이 나올때까지.
        ans = max(ans, 1LL * (i - S.top().Y) * S.top().X);
        idx = S.top().Y;
        S.pop();
      }
      S.push({h, idx}); //top보다 더 높은 h를 만나면 쌓아둔다.
    }
    while (!S.empty()) {
      ans = max(ans, 1LL * (n - S.top().Y) * S.top().X);
      S.pop();
    }
    cout << ans << '\n';
  }
}

// 풀이
// 수열이 증가할 때 : 스택에 쌓는다.
// 수열이 감소할 때 : 스택이 비거나 현재 높이보다 낮을 때까지 뽑는다.
// 끝까지 뽑는 게 아니라 현재높이 전까지만 뽑으면 되는 이유는 현재 높이가 새로운 증가수열로 커버해줄 수 있기 때문이다.
// 증가수열만 스택 안에 보관되어있으므로, 거리를 곱해주면서 직사각형 넓이를 갱신하면 된다.
// 바로 전 top은 가로길이가 1이고 그 높이만큼 온전히 보장된다.
// 전전 top은 바로 전의 top이 더 크기때문에 X2(거리)를 해도 감당이 된다.
// 모든 작업이 끝나고 스택을 비워주면서 계산을 꼼꼼하게 한다.