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

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

 

아이디어:

1. 오름차순을 유지하는 모노톤 스택

2. 스택에는 pair<높이, 사각형 등장 최초 위치> 저장

3. 결과는 long long형으로 저장 (중간에 int에서 long long으로 변환하거나 stack에 pair<long long, long long> 저장)

4. 스택에서 pop()할 때마다 top()으로 만들 수 있는 직사각형의 넓이 계산

(i - S.top().second) * S.top().first

(현재 사각형 위치) - (S.top() 사각형의 최초 등장 위치)

5. 마지막에 스택을 비우면서 남은 스택 요소들로 만들 수 있는 직사각형의 넓이 계산

(n - S.top().second) * S.top().first

(마지막 위치) - (S.top() 사각형의 최초 등장 위치)

 

S.top()은 항상 스택 내 가장 높은 사각형을 가리키고있다.

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

// Answer Code
int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	while (1) {

		int n, tmp;
		long long ans;
		cin >> n;
		stack<pair<int, int>> S;

		if (n == 0) return 0;

		ans = 0;

        for (int i = 0; i < n; i++) {
            cin >> tmp;
            int idx = i;
            while (!S.empty() && S.top().first >= tmp) {
                ans = max(ans, 1LL * (i - S.top().second) * S.top().first);
                idx = S.top().second;
                S.pop();
            }
            S.push({ tmp, idx });
        }
        while (!S.empty()) {
            ans = max(ans, 1LL * (n - S.top().second) * S.top().first);
            S.pop();
        }

		cout << ans << "\n";
	}

	return 0;

}