boj 6198 c++ [백준 6198, 옥상 정원 꾸미기]

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

int heights[80002];
long long ans = 0;

void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> heights[i];
    }
    stack<pair<int, int>> st;  // 인덱스, 높이
    for (int i = n; i > 0; --i) {  // 오른쪽 빌딩부터 탐색
        while (!st.empty() && st.top().second < heights[i]) {
            st.pop();
        }
        if (st.empty()) {
            ans += n - i;  // 현재 빌딩이 가장 높은 경우
        } else {
            ans += (st.top().first - i) - 1;  // 오른쪽에 현재 빌딩보다 높은 빌딩이 존재하는 경우
        }
        st.push({i, heights[i]});  // 현재 빌딩을 스택에 push
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}