Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Largest Rectangle in Histogram

Leetcode algorithms 第 84 题:Largest Rectangle in Histogram。

题目

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.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.

For example,
Given height = [2,1,5,6,2,3],
return 10.

解答

求直方图里的最大矩形。这题的算法非常巧妙,使用一个记录遍历过程中保持递增的元素的下标,比如在例子中,

  • 栈中的元素首先会是0。
  • 然后位置1比位置0低,于是0出栈,然后1 2 3依次入栈。
  • 然后位置4比位置3和位置2都低,位置3、位置2出栈,4入栈,栈变为1 4。
  • 然后位置5比位置4高,5入栈,栈变为1 4 5。

于是,栈中始终保持了包含当前位置在内的高度依次递增的序列。为了方便处理,在最后添加一个0,遇到这个0后,所有的元素都需要出栈,栈重新变为空。

那么这个栈有什么用呢?当新的元素比栈顶位置的元素小时,需要更新当前可以得到的最大矩形。比如当遍历到位置4时,栈中的元素为1 2 3,可以知道,单独为3可以构成一个矩形,2和3可以组成一个矩形,1、2和3也可以组合成一个矩形。但1、2、3的这种情况不用考虑,因为后面加入了一个4,1和4组合时自然把2和3包含在内了,得到的矩形也会更大,于是此时只需要考虑比位置4高的(即为位置2和3)那些即可。具体做法可以在每个元素出栈前,记录其可以得到的最大面积。

如果当前出栈的位置为t,以高度height[t]可以组成的最大矩形的长度为i- s.top() – 1,因为:

  • 根据递增性质,t后面一直到i的位置都是比height[t]大的。
  • 而t的前一个位置,即为新的栈顶s.top(),在s.top()到t之间可能已经有一些元素已经经历了入栈和出栈的动作,他们之所以出栈,是因为他们都比height[t]大,于是也可以和height[t]组成矩形。

这两部分组合在一起即为height[t]能够组成的最大矩形,此矩形的长度为 i – s.top() – 1,位置i不算,其为最新的元素,位置s.top()不算,其比height[t]小。

另外,如果出栈后栈为空,则以height[t]为高度的矩形的长度为i,因为0到i-1的位置均满足要求。

语言比较难以描述清楚,具体参考代码:

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        height.push_back(0);
        stack<int> s;
        int i = 0, ans = 0;
        while (i < height.size())
        {
            if (s.empty() || height[s.top()] <= height[i])
                s.push(i++); //入栈过程,i递增
            else
            {
                int t = s.top(); s.pop(); //出栈过程,i不变
                ans = max(ans, height[t] * (s.empty() ? i : i - s.top() - 1));
            }
        }
        return ans;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论