526互联

算法随想Day53【单调栈】| LC84-柱状图中最大的矩形

发布时间 2023-04-01 23:32:59作者: 冥紫将

int largestRectangleArea(vector& heights)
{
int result = 0;
stack st;
heights.insert(heights.begin(), 0);
heights.push_back(0);
st.push(0);

for (int i = 1; i < heights.size(); i++)
{
    if (heights[i] > heights[st.top()])
    {
        st.push(i);
    }
    else if (heights[i] == heights[st.top()])
    {
        st.pop();
        st.push(i);
    }
    else
    {
        while (!st.empty() && heights[i] < heights[st.top()])
        {
            int mid = st.top();
            st.pop();
            if (st.empty() != true)
            {
                int left = st.top();
                int right = i;
                int w = right - left - 1;
                int h = heights[mid];
                result = max(result, w * h);
            }
        }
        st.push(i);
    }
}
return result;

}