LeetCode·84.柱状图中最大的矩形·单调递增栈

链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/solution/by-xun-ge-v-626m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

 

示例

 

思路

解题思路
1. 暴力求解
**遇事不要慌，先暴力求解试试看，万一就过了呢，皆大欢喜**
当前本题过不了、、、、、、
没办法只能优化了，先说说暴力的思路，我们需要求最大面积，面积需要什么高 和 宽，那么我们直接枚举数组中所有的高和宽，然后搭配一下保存最大面积

• 枚举宽

        我们固定每个数组元素为每个矩形的高，然后遍历数组，寻找每个矩形高能构成的最大面积，当左右两边第一次出现比当前高小的元素值，即为当前高能构成的最大值，每次保存最大值

• 枚举高

        我们固定左右两边的长度即固定宽的长度，然后遍历数组，寻找当前长度中高最短的元素，即当前宽能构成的最大矩形，每次保存最大值

2. 单调栈
通过暴力解法，过不了，因为在枚举宽的同时需要寻找高，在枚举高的时候又要寻找宽，时间消耗非常大
那么可以利用递增栈优化暴力暴力求解的过程

• 当元素大于栈顶元素时，入栈
• 当元素小于栈顶元素时，维护栈的递增性，将小于当前元素的栈顶元素弹出，并计算面积

3. 单调栈+哨兵
在上面递增栈中，我们总是需要判断当前元素是否为最后元素或者为栈顶元素，很麻烦，那么可以在数组前后加上两个哨兵，充当坏点，在实际计算中不影响结果，但是简化我们的逻辑，正如我们高中或者初中学过的辅助线或者凑配法都是差不多的思路

具体实现看代码，注释超级详细

代码

1. 暴力求解

//枚举高
int largestRectangleArea(int* heights, int heightsSize){
    int max = INT_MIN;//记录最大面积
    for(int left = 0; left < heightsSize; left++)//左边宽
    {
        int minh = INT_MAX;
        for(int right = left; right < heightsSize; right++)//右边宽
        {
            minh = fmin(minh, heights[right]);//取最小高
            max = fmax(max, (right-left+1) * minh);//保存最大构成面积
        }
    }
    return max;
}

作者：xun-ge-v
链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/solution/by-xun-ge-v-626m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//枚举宽
int largestRectangleArea(int* heights, int heightsSize){
    int max = -1;//记录最大面积
    for(int mid = 0; mid < heightsSize; mid++)//
    {
        int h = heights[mid];//记录当前位置高
        int left = mid, right = mid;
        while(left-1 >= 0 && heights[left-1] >= h)//寻找最大宽度
        {
            left--;
        } 
        while(right+1 < heightsSize && heights[right+1] >= h)
        {
            right++;
        } 
        max = fmax(max, (right-left+1) * h);//保存最大面积
    }
    return max;
}

作者：xun-ge-v
链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/solution/by-xun-ge-v-626m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 

2. 单调栈

int largestRectangleArea(int* heights, int heightsSize)
{
    int stack[heightsSize];//定义栈
    int top = -1;
    stack[++top] = 0;

    int max = -1;
    for(int i = 1; i < heightsSize; i++)//遍历数组
    {
        if(heights[i] >= heights[stack[top]])//入栈
        {
            stack[++top] = i;
        }
        else
        {
            while(top != -1 && heights[i] < heights[stack[top]])//出栈并计算面积，维护递增性，需要对小于的元素全部出栈
            {
                if(top-1 == -1)//最后一个栈顶元素，出栈计算面积需要包含一下前面和后面，因为矩形可以延伸，这里需要好好想一想
                {
                    max = fmax(max, i * heights[stack[top]]);
                }
                else
                {
                    max = fmax(max, (i - stack[top] + stack[top] - stack[top-1] - 1) * heights[stack[top]]);//栈中元素，计算面积与需要延伸，能延伸多长就延伸多长
                }
                --top;
            }
            stack[++top] = i;
        }
    }
    while(top != -1)//数组元素全部遍历完了，单是栈还有元素，进行清空栈
    {
        if(top-1 == -1)
        {
            max = fmax(max, (heightsSize) * heights[stack[top]]);
        }
        else
        {
            max = fmax(max, (heightsSize - 1 - stack[top-1]) * heights[stack[top]]);
        }
        --top;
    }
    return max;
}


作者：xun-ge-v
链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/solution/by-xun-ge-v-626m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

3. 单调栈+哨兵

int largestRectangleArea(int* heights, int heightsSize)
{
    int ans[heightsSize+2];//添加哨兵
    ans[0] = 0;
    ans[heightsSize+1] = 0;
    for(int i = 0; i < heightsSize; i++)
    {
        ans[i+1] = heights[i];
    }

    int stack[heightsSize+2];//定义栈
    int top = -1;
    stack[++top] = 0;

    int max = 0;
    for(int i = 1; i < heightsSize+2; i++)
    {
        if(ans[i] >= ans[stack[top]])//入栈
        {
            stack[++top] = i;
        }
        else
        {
            while(ans[i] < ans[stack[top]])//出栈
            {
                max = fmax(max, (i - stack[top] + stack[top] - stack[top-1] - 1) * ans[stack[top]]);
                --top;
            }
            stack[++top] = i;
        }
    }
    return max;
}

作者：xun-ge-v
链接：https://leetcode.cn/problems/largest-rectangle-in-histogram/solution/by-xun-ge-v-626m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。