[백준] 1725번 히스토그램

1725번: 히스토그램

입력을 받을 때마다 stack의 top과 값을 비교해준다

 

1. top <= 입력값(height)

이전 사각형이 계속 이어질 수 있는 상태이기 때문에

그냥 stack에 입력값을 push하여 현재 사각형을 시작한다.

 

2. top > 입력값(height)

이전 사각형이 더이상 지속될 수 없는 상태이기 때문에

stack이 empty가 되거나 top <= 입력값(height) 이 될 때까지 push해준다.

 

stack에 입력값을 push해줄 때 하나 더 고려해줘야 할 사항이 있다.

바로 가로길이인 width이다.

 

그냥 현재 index값을 현재 사각형의 시작 위치로 저장해주면

이렇게 현재 위치에서부터만 시작되므로 최대 사각형을 구하지 못한다.

그래서 top > 입력값(height) 이라 pop해줄 때

pop되는 이전 사각형의 시작 위치의 값을 가져와 현재 사각형의 시작 위치로 넣어주면

이렇게 최대 직사각형을 찾을 수 있다.

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

int main() {
	int N;
	cin >> N;

	stack <int> histogram, start;
	int Max = -1, height, temp;
	histogram.push(0), start.push(0);

	for (int i = 0; i < N; i++) {
		cin >> height;
		temp = i;
		while (!histogram.empty() && histogram.top() > height) { //이전 사각형이 지속 가능한 상태가 될 때까지 pop
			Max = max(Max, histogram.top()*(i - start.top()));
			histogram.pop();
			temp = start.top(); //현재 사각형의 시작 인덱스는 이전에 시작된 걸로 볼 수 있다
			start.pop();
		}
		histogram.push(height); //현재 사각형 시작
		start.push(temp); //현재 사각형의 시작 인덱스 넣어줌
	}

	while (!histogram.empty()) {
		Max = max(Max, histogram.top()*(N - start.top()));
		histogram.pop();
		start.pop();
	}

	cout << Max;

	return 0;
}