[C/C++] BOJ 1725 :: 히스토그램

 BOJ 1725 :: 히스토그램

문제 링크 : https://www.acmicpc.net/problem/1725

모르겠어서 다른 분들이 푼 것을 참고하여 풀었다..!...

우선 규칙을 찾아내는 것이 중요한데 나는 규칙을 정말 못찾겠어가지고 ㅠ 못풀었다..

핵심적인 규칙이 되는!! 구해야할 직사각형이 결정되는 순간은

이전의 막대높이보다 현재의 막대높이가 더 낮을 때이다.

stack을 이용하여 O(N) 으로 풀 수 있다!

풀이 과정

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_1725/BOJ_1725.cpp

// 백준알고리즘 1725번 :: 히스토그램
#include<iostream>
#include<stack>
using namespace std;
#define max(a,b) a > b ? a : b
stack<int> st;
int arr[1000002];
int N = 0;
int ret = 0;
 
int main(void)
{
    cin >> N;
 
    for (int i = 1; i <= N; i++)
        cin >> arr[i];
 
    st.push(0);
    for (int i = 1; i <= N+1; i++)
    {
        while (!st.empty() && arr[st.top()] > arr[i])
        {
            int height = arr[st.top()];
            st.pop();
            int width = i - st.top()-1;
 
            ret = max(ret, height*width);
        }
        st.push(i);
    }
 
    cout << ret;
 
    return 0;
}