LeetCode 84柱状图中最大的矩形 | 代码随想录25期训练营day60 完结撒花！

单调栈3

LeetCode 84 柱状图中最大的矩形 2023.12.23

• 题目链接
• 代码随想录讲解[链接]
  

int largestRectangleArea(vector<int>& heights) {
    /*
        //双指针法，也是暴力求解的
        //result存储最终答案，即勾勒出来的矩形最大面积
        int result = 0;
        //minleft、minright数组分别记录索引i左侧或右侧第一个比height[i]小的值的索引
        //minleft[0]需要初始化为-1，其他值会被覆盖
        //minright[heights.size()-1]需要初始化为heights.size()，其他值会被覆盖
        vector<int> minleft(heights.size(), -1);
        vector<int> minright(heights.size(), heights.size());
        for (int i = 1; i < heights.size(); i++)
        {
            //用temp变量记录左侧第一个比height[i]小的值的索引
            int temp = i-1;
            while (temp >= 0 && heights[temp] >= heights[i])
                temp = minleft[temp];
            //将temp存入数组中，记录为当前索引值对应的左侧第一个比其小的数的索引
            minleft[i] = temp;
        }
        for (int i = heights.size()-2; i >= 0; i--)
        {
            //用temp变量记录右侧第一个比height[i]小的值的索引
            int temp = i+1;
            while (temp < heights.size() && heights[temp] >= heights[i])
                temp = minright[temp];
            //将temp存入数组中，记录为当前索引值对应的右侧第一个比其小的数的索引
            minright[i] = temp;
        }
        //遍历求解最大矩形面积
        for (int i = 0; i < heights.size(); i++)
        {
            //宽
            int l = minright[i] - minleft[i] - 1;
            //高
            int h = heights[i];
            //更新result为遍历最大值
            result = result < l*h ? l*h : result;
        }
        return result;
        */

    //单调栈法
    //result存储最终答案，即勾勒出来的矩形最大面积
    int result = 0;
    //数组头部加入元素0，为了保证前两个柱体可能为最大解
    heights.insert(heights.begin(), 0);
    //数组尾部加入元素0，为了保证后两个柱体可能为最大解
    heights.push_back(0);
    //创建单调栈存储已经遍历过的元素的索引，且该栈元素呈单调递减
    stack<int> st;
    st.push(0);
    for (int i = 1; i < heights.size(); i++)
    {
        //当前柱高大于栈顶索引对应的柱高，因为提前已经头部加入0所以栈内一定元素大>=2
        while (heights[st.top()] > heights[i])
        {
            //heights[i]<height[st.top()],栈的下一个索引对应值也小于height[st.top()]
            int mid = st.top();
            st.pop();
            int l = i - st.top() - 1;//宽
            int h = heights[mid];//此时的极大值，高
            //更新result为遍历最大值
            result = result < l*h ? l*h : result;
        }
        st.push(i);
    }
    return result;
}