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
반응형