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

step 1

정답이 되는 직사각형은 위, 아래, 좌우로 더이상 확장이 불가능한 상태여야 합니다.

히스토그램의 각 막대에 대해서 '해당 막대를 완전해 포함할 때 직사각형의 최대 면적'을 구한 다음 그 중 가장 큰 것을 고르면 됩니다.

step 2

막대가 정해졌다면 사실 높이가 정해진 것과 같습니다. 그럼 좌, 우로 얼마나 확장 가능한지만 남아 있습니다. 오른쪽으로만 확장한다고 생각해 봅시다.

스택을 하나 만든 다음 왼쪽부터 오른쪽으로 쭉 보면서 다음 규칙에 따라 스택에 막대를 넣고 뺍니다.

1. 스택의 가장 위 막대의 높이가 지금 보고 있는 막대의 높이보다 크다면 스택에 있는 막대는 오른쪽으로 더이상 확장하지 못한다는 뜻입니다. 해당 막대를 스택에서 빼고 그 막대가 오른쪽으로 얼마나 확장했는지 기록합니다.
2. 스택의 가장 위 막대의 높이가 이번에 넣을 막대의 높이보다 작거나 같다면 스택 안에 있는 모든 막대들은 오른쪽으로 한칸 더 확장할 수 있다는 뜻입니다. 지금 보고 있는 막대를 스택에 넣어줍니다.

제일 처음과 끝에는 높이 0짜리 막대가 있다고 생각하면 계산하기 조금 더 편해집니다.

코드

#include<stdio.h>
#include<stack>
using namespace std;
stack<pair<long long int, long long int> > s;
long long int b[200000],c[5][200000];
int main() {
	long long int n, m,i;
	while (1) {
		scanf("%lld", &n);
		if (n == 0) break;
		for (i = 1; i <= n; i++) scanf("%lld", &b[i]);
		b[n + 1] = -1;
		b[0] = -1;
		for (i = 1; i <= n+1; i++) {
			while (1) {
				if (s.size() == 0 || s.top().first <= b[i]) { s.push(make_pair(b[i], i)); break; }
				c[1][s.top().second] = i - s.top().second;
				s.pop();
			}
		}
		for (i = n; i >= 0; i--) {
			while (1) {
				if (s.size() == 0 || s.top().first <= b[i]) { s.push(make_pair(b[i], i)); break; }
				c[2][s.top().second] = s.top().second - i;
				s.pop();
			}
		}
		s.empty();
		long long int max = -1;
		for (i = 1; i <= n; i++) {
			if (max < (c[1][i] + c[2][i] - 1)*b[i]) max = (c[1][i] + c[2][i] - 1)*b[i];
		}
		printf("%lld\n", max);
	}
	return 0;
}