首页 > 数据结构 > 线性结构 > LeetCode-Largest Rectangle in Histogram[栈]
2014
11-18

LeetCode-Largest Rectangle in Histogram[栈]

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.

标签: Array Stack
分析

简单的,类似于 Container With Most Water(\S \ref{sec:container-with-most-water}),对每个柱子,左右扩展,直到碰到比自己矮的,计算这个矩形的面积,用一个变量记录最大的面积,复杂度$O(n^2)$,会超时。

如图\S \ref{fig:histogram-area}所示,从左到右处理直方,当$i=4$时,小于当前栈顶(即直方3),对于直方3,无论后面还是前面的直方,都不可能得到比目前栈顶元素更高的高度了,处理掉直方3(计算从直方3到直方4之间的矩形的面积,然后从栈里弹出);对于直方2也是如此;直到碰到比直方4更矮的直方1。

这就意味着,可以维护一个递增的栈,每次比较栈顶与当前元素。如果当前元素大于栈顶元素,则入栈,否则合并现有栈,直至栈顶元素小于当前元素。结尾时入栈元素0,重复合并一次。

代码1

// LeetCode, Largest Rectangle in Histogram
// 时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        stack<int> s;
        height.push_back(0);
        int result = 0;
        for (int i = 0; i < height.size(); ) {
            if (s.empty() || height[i] > height[s.top()])
                s.push(i++);
            else {
                int tmp = s.top();
                s.pop();
                result = max(result,
                        height[tmp] * (s.empty() ? i : i - s.top() - 1));
            }
        }
        return result;
    }
};

Java代码:

public class Solution {
   
    
    public static int largestRectangleArea (int heights[]){
        if(heights.length == 0 ) return 0;
        if(heights.length == 0) return heights[0];
        int ans = 0;
        int n = heights.length;
        int left[] = new int[n+1];
        int right[] = new int[n+1];
        processLR(heights, left, right);
        for(int i=1; i<=n; i++){
            int tmp = (right[i]-left[i]+1) * heights[i-1];
            if( ans < tmp)
                ans = tmp;
        }

        return ans;
    }

    public static int processLR(int heights[], int left[], int right[]){
        int n = heights.length;
        //用临时数组,设置两个哨兵
        int tempArr[] = new int[n+2];
        tempArr[0] = -1;
        for(int i=1; i<=n; i++) tempArr[i] = heights[i-1];
        tempArr[tempArr.length-1] = -1;

        for(int i=1; i<=n; i++){
            int k = i;
            while( tempArr[i] <= tempArr[k-1])
                k = left[k-1];
            left[i] = k;
        }

        for(int i=n; i>0; i--){
            int k = i;
            while(  tempArr[i] <= tempArr[k+1])
                 k = right[k+1];
            right[i] = k;
        }


        return 0;
    }
}

  1. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1

  2. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  3. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  4. 这道题目虽然简单,但是小编做的很到位,应该会给很多人启发吧!对于面试当中不给开辟额外空间的问题不是绝对的,实际上至少是允许少数变量存在的。之前遇到相似的问题也是恍然大悟,今天看到小编这篇文章相见恨晚。