6549번

6549번 - 히스토그램에서 가장 큰 직사각형

이 문제는 종만북에서 분할정복, 스택을 이용한 문제풀이가 나와있는데, 

나는 스택을 이용해서 문제를 풀어보았다. 접근법을 보고 이해하면서 문제를 풀었다.

어떻게 이런방법을 생각해서 푸는지, 아직 나는 저런 생각을 못하겠다. 

다음에는 분할정복 방법으로 풀어봐야겠다.. 

일단 이 문제는 x라는 높이의 직사각형에서 왼쪽으로 최대, 오른쪽으로 최대를 구해서 직사각형의 최대값을 구하는 방법이다.

어떤 사각형에서 자신보다 높이가 낮으면, 왼쪽,오른쪽으로 확장해갈 수 없다는 점을 이용했다.

따라서 그때, 직사각형의 최대값을 구하고면서 계속해서 스택에 최대값이 계산되지 않은 직사각형을 쌓게 된다.

따라서 스택에는 점점 커지는 직사각형이 쌓이게 된다, 마치 오름차순으로 쌓이듯

그러면서 계산을 해주면 된다.

내가 아직 제대로 설명을 하지 못한다...는 것은 다시 풀어보고 완벽하게 익히기

<정답 코드 - 스택>

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
 
int main()
{
    int N;
    while ((cin >> N) && N!=0)
    {
        vector<long long> height;
        stack<int> st;
 
        long long ans = 0;
 
        height.resize(N+2);
        height[0] = 0;
        height[N + 1] = 0;
 
        for (int i = 1; i <= N; i++)
        {
            cin >> height[i];
        }
 
        for (int i = 1; i <= N+1; i++)
        {
            while (!st.empty())
            {
                int top = st.top();
                int left;
 
                if (height[top] >= height[i])
                {
                    st.pop();
 
                    if (st.empty())
                    {
                        left = 0;
                    }
                    else
                    {
                        left = st.top();
                    }
                    
                    ans = max(ans,((i - left - 1)*height[top]));
                }
                else
                {
                    break;
                }
 
            }
            st.push(i);
        }
        cout << ans << endl;
    }
 
 
    return 0;
}