PS/백준 알고리즘[BOJ]

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

BE_개발자 2023. 10. 28. 23:26
728x90
반응형

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

 

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

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤

www.acmicpc.net

#define F first
#define S second
#include<iostream>
#include<stack>
using namespace std;
stack<pair<long long, int>> sta;

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(NULL);
	long long int max, s, h;
	int n;
	while (1) {
		cin >> n;
		if (n == 0) break;
		max = 0;
		for (int i = 0; i <= n; i++) {
			if (i == n) h = 0;
			else cin >> h;
			int temp;
			if (sta.empty() || h > sta.top().F) sta.push({ h, i });
			else if (h < sta.top().F) {
				while (!sta.empty() && h <= sta.top().F) {
					s = (i - sta.top().S) * sta.top().F;
					if (s > max) max = s;
					temp = sta.top().S;
					sta.pop();
				}
				sta.push({ h, temp });
			}
		}
		cout << max << "\n";
		while (!sta.empty()) sta.pop();
	}
	return 0;
}

728x90
반응형