力扣84柱状图中最大的矩形

力扣84柱状图中最大的矩形

题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积

输入输出样例

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

输入： heights = [2,4]
输出： 4

算法1：暴力解法，控制高度，移动边

    //使用暴力解法，枚举每个矩阵的高度
    //固定高度再寻找两边大于该盖高度的坐标
    //相当于中心扩散的方法
    int largestRectangleArea(vector<int>&height)
    {
    
        int length=height.size();
        int maxArea=0;

        if(length==0)
        {
    
            return 0;
        }
        else if(length ==1)
        {
    
            return height[0];
        }

        for(int i=0;i<length;i++)
        {
    
            int right=i,left=i;
            //寻找左边界
            while(left>=0&&height[left]>=height[i])
            {
    
                left--;
            }
            while(right<length&&height[right]>=height[i])
            {
    
                right++;
            }
            
            int area=(right-left-1)*height[i];
            maxArea=max(maxArea,area);
        }
        return maxArea;

    }

解法2，单调栈

//使用单调栈的思想
    int largestRectangleArea2(vector<int>&height)
    {
       
        int length=height.size();
        if(length==0)
        {
    
            return 0;
        }

        int maxArea=0;
        //建立堆栈,堆栈保存坐标
        stack<int>stk;

        for(int i=0;i<length;i++)
        {
    
            //当堆栈不为空，且栈顶元素要大于当前的值,便可以计算当前的位置
            while(!stk.empty()&&height[stk.top()]>height[i])
            {
    
                //栈顶元素的值就是高度
                int high=height[stk.top()];
                //栈顶元素出栈
                stk.pop();
                //记录当前的位置
                int width=i;
                if(!stk.empty())
                {
    
                    //因为当前的元素出栈了
                    width=i-stk.top()-1;
                }
                maxArea=max(maxArea,high*width);
            }
            //将满足递增的元素入栈
            stk.push(i);
        }

        //遍历完成后
        //对栈不为空的情况进行讨论
        while(!stk.empty())
        {
    
            int high=height[stk.top()];
            stk.pop();
            int width=length;
            if(!stk.empty())
            {
    
                width=length-stk.top()-1;
            }
            maxArea=max(maxArea,high*width);
        }
        return maxArea;    
    }

解法3：单调栈和哨兵

    //解法3：单调栈和哨兵的结合
    int largestRectangleArea3(vector<int>&height)
    {
    
        int length=height.size();
        if(length==0)
        {
    
            return 0;
        }

        int maxArea=0;
        //设置哨兵数组
        vector<int>newHeight(length+2);
        for(int i=0;i<length;i++)
        {
    
            newHeight[i+1]=height[i];
        }
        newHeight[0]=0;
        newHeight[length+1]=0;

        //更新length和height数组
        length+=2;
        height=newHeight;

        //建立堆栈
        stack<int>stk;
        //将哨兵压入栈中
        stk.push(0);


        //查找最大面积
        for(int i=1;i<length;i++)
        {
    
            //当栈顶元素大于当前值时
            while(height[stk.top()]>height[i])
            {
    
                int high=height[stk.top()];
                stk.pop();
                int width=i-stk.top()-1;
                maxArea=max(maxArea,high*width);
            }
            stk.push(i);
        }
        return maxArea;
    }