[BOJ 백준] 1725번 히스토그램

문제

BOJ 1725 : https://www.acmicpc.net/problem/1725

1725번: 히스토그램

접근

백준 님의 문제 풀이 설명글에서 힌트를 얻어 문제를 해결하였다. 분할 정복을 이용하는 방법과 스택을 이용하여 문제를 해결하는 방법이 상세하게 설명되어있다.

코드

#include<algorithm>
#include<iostream>
#include<stack>

using namespace std;

int n, ans = 0, top, arr[100005];
stack<int> s;

int main() {
	cin >> n;
	s.push(0);
	arr[0] = 0;
	arr[n + 1] = 0;

	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	for (int i = 1; i <= n + 1; i++) {
		while (!s.empty() && arr[s.top()] > arr[i]) {
			top = s.top();
			s.pop();
			ans = max(ans, arr[top]*(i - s.top() - 1));
		}
		s.push(i);
	}
	cout << ans;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study