[c++] LeetCode 84번 Largest Rectangle in Histogram

stack에 (height, index) 를 쌍으로 저장해준다.

heights를 순회하면서  stack의 top 보다 현재 height가 크다면 stack에 push해서 넣어준다.
만약 stack의 top보다 현재 height가 작다면 이 height 보다 작은 top이 나올 때 까지 pop을 해주고,
pop을 하면서 height와 index로 직사각형의 너비를 계산해준다.

top.height * ( i - top.index ) 가 직사각형의 너비가 되고 answer에 max를 취해서 큰 값만 가져간다.
현재 height보다 작은 top을 만났을 때, 다시 push를 해줘야하는데, 이때의 index는 현재 index가 아니라 마지막에 pop한 top의 index가 되어야한다. 왜냐하면 마지막에 pop한 top부터 너비가 계산되기 때문이다.

class Solution
{
public:
    int largestRectangleArea(vector<int> &heights)
    {
        int minHeight = heights[0];
        int l = 0;
        int answer = heights[0];
        stack<pair<int, int>> s;
        s.push({heights[0], 0});

        for (int i = 1; i < heights.size(); i++)
        {
            pair<int, int> top = s.top();
            if (s.empty() || top.first <= heights[i])
            {
                s.push({heights[i], i});
            }
            else
            {
                pair<int, int> top = s.top();
                int idx = i;
                while (!s.empty() && top.first > heights[i])
                {
                    idx = top.second;
                    answer = max(answer, top.first * (i - top.second));
                    s.pop();
                    if (!s.empty())
                    {
                        top = s.top();
                    }
                }
                s.push({heights[i], idx});
            }
        }
        while (!s.empty())
        {
            pair<int, int> top = s.top();
            answer = max(answer, top.first * ((int)heights.size() - top.second));
            s.pop();
        }
        return answer;
    }
};