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

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

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

#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;
}