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

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다.

 

이 문제는 주어진 히스토그램에서 넓이가 가장 큰 직사각형을 구하는 문제입니다.

 

n이 10만 까지있으므로 당연히 모든 넓이를 다 해보는 방법으로는 해결을 할 수 없습니다.

 

따라서 저는 이 문제를 스택을 이용하여 해결을 하였습니다.

 

스택을 이용하여 높이가 스택의 top보다 높으면 계속 진행하고 그렇지 않으면 현재 집어넣을 높이보다 높이가 낮아질 때까지 pop하면서 그사이에 존재하는 직사각형의 넓이를 계산해주면서 끝까지 진행해주면 답을 찾을 수 있습니다.

 

넓이를 계산할 때 현재 높이에 해당하는 부분은 s.top 부분이고

밑변에 해당하는 부분은 top의 원소를 빼준뒤 그다음 top원소가 존재하는 밑변의 좌표까지가 됩니다.

 

예를 들어 이런 상태에서 스택을 pop 한다고하면 밑변의 길이가 7인 부분의 직사각형은 4일때까지의 길이인 3*높이를 해주어야 합니다. 그 이유는 비어있는 부분은 모두 6-7보다 높이가 높았기 때문에 공간이 비어있으므로 밑변의 길이는 현재 넣을 길이인 x-1에서 스택을 하나 pop해주고 난뒤의 밑변의 길이를 빼주어야 합니다.

 

따라서 이런식으로 끝까지 진행을 하고 마지막에 도달하면 남은 스택이 빌때까지 pop을 진행하면 최종 넓이를 O(N)만에 구할 수 있습니다.

 

다음은 코드입니다.

 

#include <iostream>
#include <stack>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	
	while(1) {
		int n; cin >> n;
		stack<long long> s; // 밑변 저장 
		long long arr[100001] = {0, };
		long long ans = 0;
		if(n == 0)
			break;
		
		for(int i = 1; i <= n; i++)
			cin >> arr[i];
		
		s.push(0);
		
		for(int i = 1; i <= n+1; i++) {
				while(!s.empty() && arr[s.top()] > arr[i]) {
					long long height = s.top();
					s.pop();
					long long x = i-1-s.top();
					ans = max(ans, x*arr[height]);
				}
				s.push(i);
			}
		cout<<ans<<'\n';	
		}	
	return 0;
}