[Leetcode] largest-rectangle-in-histogram

문제링크

[문제이해]

다음과 같이 높이가 주어졌을때 가장큰 직사각형의 넓이를 구하면 되는문제다.
이문제에 대해서 브루트포스하게 풀게 되면 O(N^2)이 발생하게 된다.
조건이 1 <= heights.length <= 10^5 이므로 시간초과가 발생하니 조금더 효율적으로 처리 할 필요가 있다.

[접근]

상황을 나눠서 정리해보자.

먼저 브루트포스 방식으로 접근하게 된다면 다음과 같다.
5부터 읽기 시작한다고 했을때 5를 시작점으로 5보다 크거나 같은 막대까지만 sequence하게 접근해서 넓이=5 X 2=10이다. 즉 5보다 작은 2와 3은 필요가 없게된다.
6인시점에서는 6 X 1=6이다.
2인 시점에서는 3이 2보다 크니 2X4=8이다. (5와6은 2보다 작으니)
3인 시점에서는 3X1=3이다.
즉 최대넓이는 10이 된다.

어떤 도형의 시점에서 그 높이를 가진 최대 사각형의 크기를 구하는데 있어 그것보다 작은 막대의 정보는 필요하지 않다.(
즉 이를 최대한 Memorization하는 방식으로 구해보자. 세가지 경우를 생각해보자.

현재 막대를 기준으로..
1. 이전 막대보다 큰막대가 나올경우

• 큰 막대 일경우 이전에 나온막대의 높이를 포함함과 동시에 계속 사용된다.

2. 이전 막대보다 작을 경우

• 이전 막대 보다 작을경우 그 이전의 막대는 현재막대를 기준으로 높이는 사용되지 않는다. 그래서 이전 막대를 포함한 가장 넓은 사각형의 넓이를 구한후 컨테이너에서 제거 해준다.이때 제거할때 현재들어오는 포지션의 위치를 바꿔준다.(넓이 구하기 위해서)

3. 이전 막대랑 같을 경우 그냥 넘어간다.

이를 바탕으로 이를 살펴보자

다음과 같은 높이의 히스토그램이 있을때 index별로 살펴보자.
index=0~2일경우
max_size=0(아직 계산안함)
stack=[{0(시작지점),3(높이)]

index=3일경우
index3인지점 보다 높이가 큰(높이 2보다 큰) 이전것들 다 제거하고 넓이 계산
max_size=9,
stack=[{0(시작지점),2(높이)]: 포지션위치를 제거 시점까지로 바꿔줬다.

index=4일경우
index4인지점 보다 높이가 큰 이전것들 다 제거하고 넓이 계산
2(이전 인덱스 높이)*(4(현재 인덱스위치)-0(이전 높이 의 시작 인덱스))=8이다. 즉 max_size인 9보다 작으므로 변하지 않는다.

stack=[{0(시작지점),1(높이)]: 포지션위치를 제거 시점까지로 바꿔줬다.

**다읽은후
컨테이너에 남은 것들을 전부 계산하고 max_size를 비교하고 제거한다.
stack[{0(시작지점),1(높이)}]을 처리해줘야한다.
(5(길이)-0(시작지점))X1(높이)=5이다
이떄 max_size인 9보다 작기에 변하지 않는다.

[구현]

#include <bits/stdc++.h>
using namespace std;
#define Pair pair<int, int>
#define pos first
#define height second
class Solution
{
public:
    int largestRectangleArea(vector<int> &heights)
    {
        int __maxSize = 0, pos_length = heights.size();
        stack<Pair> st;
        for (int pos = 0; pos < pos_length; pos++)
        {
            int cur_height = heights[pos];
            if (!st.empty() && cur_height == st.top().height)
                continue;
            else
            {
                int next_pos = pos;
                while (!st.empty() && st.top().height > cur_height)
                {
                    Pair next = st.top();
                    next_pos = next.pos;
                    st.pop();
                    // int before = st.empty() ? 0 : st.top().pos;
                    __maxSize = max(__maxSize, (pos - next_pos) * next.height);
                }
                if (!st.empty() && cur_height == st.top().height)
                    continue;
                st.push({next_pos, cur_height});
            }
        }
        while (!st.empty())
        {
            Pair next = st.top();
            st.pop();
            __maxSize = max(__maxSize, (pos_length - next.pos) * next.height);
        }
        return __maxSize;
    }
};
int main()
{
    vector<int> vec({2, 1, 5, 6, 2, 3});
    vector<int> vec2({5, 4, 1, 2});
    Solution *solution = new Solution();
    cout << solution->largestRectangleArea(vec) << endl;
    cout << solution->largestRectangleArea(vec2) << endl;
}