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

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
int n;
int height[100002];
stack<int> highestIndexStack;

int main() {
	while (true) {
		scanf("%d", &n);
		if (n == 0) return 0;

		for (int i = 0; i < n + 2; i++) height[i] = 0;
		for (int i = 1; i <= n; i++) scanf("%d", &height[i]);

		long long result = 0;
		int now = 0;
		highestIndexStack.push(0);
		for (int i = 1; i <= n + 1; i++) {
			while (true) {
				if (highestIndexStack.size() == 0) break;

				int prevIndex = highestIndexStack.top();
				if (height[prevIndex] < height[i]) {
					break;
				}
				highestIndexStack.pop();
				if (highestIndexStack.size() > 0) {
					long long nowArea = (long long)height[prevIndex] * (long long)(now - highestIndexStack.top());
					if (nowArea > result) result = nowArea;
				}
			}
			highestIndexStack.push(i);
			now++;
		}
		cout << result << endl;
	}
	return 0;
}

예전에 책에서 봤다가, O(n^2) 일거 같은게 O(n)으로 풀리는게 당시에 엄청 문화충격이여서 몇번 풀었었다.

덕분에 기억이 나서 풀 수 있었던 문제.

i = 1..N 에 대하여,

height[i]가 스택의 top()에 있는 인덱스의 높이보다 낮을 경우, 그 값들을 빼면서 넓이 계산.

이걸 height[스택.top()] 보다 height[i]가 더 높을때까지 빼면서 계산

그 후 스택에 i를 넣는다

스택에는 높이가 아니라 index를 저장했고, 

스택의 첫 부분에 0을 넣고, 맨 뒤에도 0을 넣음으로써 마지막에 스택에서 왕창 빼면서 넓이를 계산할 수 있게 하였다.

너무나 유명한 문제니까 이만 말을 줄이겠다... ㅋㅋㅋㅋ