히스토그램

직사각형들의 높이가 주어졌을 때 가장 큰 넓이의 직사각형을 구하면 된다.

두가지 풀이가 있는데 이번에는 스택을 이용해서 풀고 다음에 다른 풀이로 풀어보겠다.

 

스택을 이용해서 앞에서부터 높이를 하나씩 볼 때 새로 들어온 높이 값이 이전 높이보다 크면 스택에 높이를 넣어준다.

이전 높이보다 작으면 이전의 더 큰 높이들은 앞으로의 직사각형에 영향을 미치지 않기 때문에 지금 새로 들어온 높이보다 작아질 때까지 스택에서 pop을 해주면서 직사각형의 넓이들을 구한다.

#include<stdio.h>
#include<stack>
using namespace std;
int N;
long long ans=0;
long long arr[3000004];
stack<int> st;
int main()
{
    scanf("%d",&N);
    st.push(0);
    for(int i=1;i<=N+1;i++)
    {
        scanf("%lld",&arr[i]);
        if(st.empty()) st.push(i);
        else{
            if(arr[st.top()]<=arr[i])
            {
                st.push(i);
            }
            else
            {
                while(!st.empty() && arr[st.top()]>arr[i])
                {
                    int ind = st.top();
                    st.pop();
                    long long x = (i-st.top()-1)*arr[ind];
                    if(ans<x) ans = x;
                    if(st.empty()) break;
                }
                st.push(i);
            }
        }
    }
    printf("%lld",ans);
}

처음에 push 0을 하고 N+1번 반복문을 도는 이유는 N번 돌고 끝났을 때 스택에 높이들이 남아있으면 안되기 때문에 0을 하나 넣어놓고 모든 높이들에 대해 직사각형의 최대 넗이를 구하기 위해서이다.