[BOJ] 6549 : Largest Rectangle in a Histogram - travelbeeee

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

참고 : https://blog.encrypted.gg/135

---

스택

너무 안풀려서 발킹도그님의 블로그를 참고했습니다.

 

스택을 이용하면 O(N) 만에 앞에서부터 순회하며 문제를 해결할 수 있습니다.

● 현재 스택의 top 보다 높이가 큰 Histogram 은 높이와 인덱스를 스택에 추가해줍니다.

( 따라서, 스택에는 높이가 증가하는 순서대로 쌓여있습니다. )

● 현재 스택의 top보다 높이가 작거나 같은 Histogram 이 들어왔을때는 다음과 같은 과정을 반복합니다.

1) 현재 top의 값보다 Histogram 의 높이가 커질 때까지 답을 갱신하며 pop을 진행한다. 이때, 스택에는 높이가 커지는 순으로 값이 쌓여있으므로 현재 높이 * 스택에서 꺼낸 블록의 수 로 최대 넓이를 구할 수 있습니다.

ex)  3 - 4 - 5 가 있으면 우리는 높이 4를 선택할거면 높이 5까지 같이 선택해서 4 * 2 의 넓이를 얻는게 최대값이고, 높이 3도 마찬가지로 높이 3을 선택할거면 4, 5 도 같이 선택해서 3 * 3 의 넓이를 얻는게 최대값이 됩니다.

2) 1)의 과정을 진행하며 현재 Histogram 보다 크거나 같은 마지막 Histogram 의 index를 지금 높이와 같이 스택에 Push 해줍니다. 이 과정이 가장 중요한데, 예를 들어 3 - 4 - 5 - 2 가 있다면 우리는 2를 만났을 때, 현재 스택의 top 보다 높이가 작거나 같은 Histogram 이 들어왔으므로 1)의 과정을 수행해야합니다. 따라서, 5 * 1, 4 * 2, 3 * 3 으로 넓이를 구해가며 최대 넓이를 갱신하고, 이제 높이가 2인 Histogram 을 스택에 Push해줘야하는데 생각해보면 3 - 4 - 5 는 높이 2보다 다 크거나 같으므로 높이 2를 포함해서 최대 넓이를 구하려면 3 - 4 - 5 를 무조건 포함해서 히스토그램의 갯수를 늘려줘야 합니다. 따라서, 높이가 2인 Histogram을 3 - 4 - 5 를 포함한 index로 스택에 Push 해줍니다.

#include<iostream>
#include<stack>
#include<algorithm>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, height[100000] = {};
	while (true) {
		cin >> N;
		if (N == 0)
			break;
		for (int i = 0; i < N; i++)
			cin >> height[i];

		long long ans = 0;
		stack<pair<int, int>> s;
		for (int i = 0; i < N; i++) {
			int point = i;
			while (!s.empty() && s.top().first >= height[i]) { 
				ans = max(ans, 1LL * (i - s.top().second) * s.top().first); 
				point = s.top().second;
				s.pop();
			}
			s.push({ height[i], point });
		}
		while (!s.empty()) {
			ans = max(ans, 1LL * (N - s.top().second) * s.top().first);
			s.pop();
		}
		cout << ans << '\n';
	}
	return 0;
}

---