[백준][C++] 6549: 히스토그램에서 가장 큰 직사각형

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

(동일한 문제: https://www.acmicpc.net/problem/1725)

 

저를 고통에 빠트리는 웰노운 문제입니다. 문제는 단순한데 풀이를 생각하기가 좀 힘듭니다.

대표적 해법은 세그먼트 트리 / 분할정복 / 스택이 있습니다. 풀이는 백준 블로그에 자세하게 정리되어 있으니 참고해주세요.

 

#pragma GCC optimize ("Ofast")
#define _CRT_SECURE_NO_WARNINGS
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING

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

typedef long long ll;


int n;
ll heights[100000];

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	
	while (cin >> n) {
		if (n == 0) break;

		for (int i = 0; i < n; ++i)
			cin >> heights[i];

		ll max_rect = 0;
		stack<int> st;	// idx
		for (int i = 0; i < n; ++i) {
			while (!st.empty() && heights[i] < heights[st.top()]) {
				ll height = heights[st.top()];
				st.pop();

				ll width = i;
				if (!st.empty())
					width = i - st.top() - 1;

				max_rect = max(max_rect, width * height);
			}
			st.push(i);
		}

		while (!st.empty()) {
			ll height = heights[st.top()];
			st.pop();

			ll width = n;
			if (!st.empty())
				width = n - st.top() - 1;

			max_rect = max(max_rect, width * height);
		}

		cout << max_rect << '\n';
	}

	return 0;
}

스택을 이용해 풀었습니다