欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Largest Rectangle in Histogram

程序员文章站 2022-06-17 22:54:47
...

1,题目要求

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Largest Rectangle in Histogram

Largest Rectangle in Histogram

给定n个非负整数表示直方图的条形高度,其中每个条形的宽度为1,找到直方图中最大矩形的区域。

2,题目思路

对于这道题,是求出一个直方图中可以找到的最大的矩形面积。

在一个直方图中,对于第i个柱子,由它往左右扩展的最大的矩形的宽度为:right - left -1
其中:

  • left:在i的左侧第一个比其矮的柱子的下标
  • right:在i的右侧第一个比其矮的柱子的下标

由题目中的例子我们有:
对于柱子6,左边第一个比它矮的,自然是5,下标为2
而右边第一个比它矮的,则是2,下标位4
于是,以柱子6出发的最大矩形,高度为6,长度为4-2-1 = 1

再比如,对于柱子5,左边第一个比它矮的,是1,下标为1
右边第一个比它矮的,则是2,下标为4
于是,以柱子5出发的最大矩形,高度为5,长度为4-1-1 = 2
符合事实。

算法具体实现逻辑见代码注释部分。

3,代码实现

static const auto s = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();


class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int maxArea = 0;
        heights.push_back(0);    //在末尾虚构一个高度为0的柱子,用于对总的情况的检查
        vector<int> index;
        for(int i = 0;i<heights.size();i++){
            //i说明当前i位置之前有柱子(只有第一个柱子才会有size为0),
            //并且,当前柱子的高度比其哪一个柱子矮,
            //说明前面柱子所能达到的最大值已经可以尝试计算了
            while(index.size()!=0 && heights[index.back()] >= heights[i]){
                //取当前最高的(最后一个)柱子的高度来计算最大面积
                //之所以是合理的,是因为我们在加入柱子的索引到index时
                //一定是按照柱子高度从低到高加入的
                //如果遇到两柱子相邻却变矮,则一定会进入while来计算这个面积
                int currH = heights[index.back()];
                index.pop_back();   //获得高度之后,删除当前最高柱子的索引
                
                //获得刚才最高的柱子前面一个柱子、
                //也即当前所有柱子里面最高的柱子的索引
                //即可以构成的、合法的举矩形的前一个位置
                //就是刚才最高柱子左侧最近的较矮柱子的下标
                //对于第一个柱子,我们需要单独判断, 并设置-1作为虚拟的、0的前一个位置
                //为了方便理解,定义右侧最近的比当前柱子矮的下标
                int rightLowerIdx = i;
                int leftLowerIdx = index.size() == 0? -1 : index.back();
                maxArea = max(maxArea, currH * (rightLowerIdx - leftLowerIdx - 1));
            }
            //将当前的下标加入
            index.push_back(i);
        }
        return maxArea;
    }
};