首页 > ACM题库 > LeetCode > 直方图最大面积-Largest Rectangle in Histogram
2014
09-05

直方图最大面积-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.

histogram

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

histogram_area

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.

题目链接:https://oj.leetcode.com/problems/largest-rectangle-in-histogram/

HOJ:http://www.acmerblog.com/hdu-1506-Largest-Rectangle-in-a-Histogram-2063.html

此题也经典的一个题,就是求出一个最大的矩形面积。

解法一

使用动态规划,用left[i]表示第i个柱子可以最多向左延伸至第left[i]个柱子,形成一个矩形,right[i]则表示向右延伸。遍历两次,分别计算出这两个数组。

再遍历一次,即可求出所有的柱子可以形成的最大的矩形面积。为了减少边界的判断,可以使用哨兵,在两端添加两个柱子高度都为-1.

//============================================================================
// Name        : MaxRectagle.java
// Author      : GaoTong
// Date        : 2014/9/5
// Copyright   : www.acmerblog.com
//============================================================================
public class MaxRectagle {
    public static void main(String args[]){
        int height[] = {2,1,5,6,2,3};
        int ans = getMaxRectangle(height);
        System.out.println(ans);
    }

    public static int getMaxRectangle (int heights[]){
        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 void 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;
        }
    }
}

算法的时间复杂度为 O(n)。 再求left[]和right[]时,虽然里面有while循环,但可以保证复杂度为O(n)

方法二

在网上发现另外一个使用一个栈的O(n)解法,代码非常简洁,栈内存储的是高度递增的下标。对于每一个直方图高度,分两种情况。1:当栈空或者当前高度大于栈顶下标所指示的高度时,当前下标入栈。否则,2:当前栈顶出栈,并且用这个下标所指示的高度计算面积。而这个方法为什么只需要一个栈呢?因为当第二种情况时,for循环的循环下标回退,也就让下一次for循环比较当前高度与新的栈顶下标所指示的高度,注意此时的栈顶已经改变由于之前的出栈。

Java代码:

  // O(n) using one stack
  public int largestRectangleArea(int[] height) {
    // Start typing your Java solution below
    // DO NOT write main() function
    int area = 0;
    java.util.Stack<Integer> stack = new java.util.Stack<Integer>();
    for (int i = 0; i < height.length; i++) {
      if (stack.empty() || height[stack.peek()] < height[i]) {
        stack.push(i);
      } else {
        int start = stack.pop();
        int width = stack.empty() ? i : i - stack.peek() - 1;
        area = Math.max(area, height[start] * width);
        i--;
      }
    }
    while (!stack.empty()) {
      int start = stack.pop();
      int width = stack.empty() ? height.length : height.length - stack.peek() - 1;
      area = Math.max(area, height[start] * width);      
    }
    return area;
  }

时间复杂度也为O(n)

参考:http://blog.csdn.net/abcbc/article/details/8943485


  1. 嗯 分析得很到位,确实用模板编程能让面试官对你的印象更好。在设置辅助栈的时候可以这样:push时,比较要push的elem和辅助栈的栈顶,elem<=min.top(),则min.push(elem).否则只要push(elem)就好。在pop的时候,比较stack.top()与min.top(),if(stack.top()<=min.top()),则{stack.pop();min.pop();},否则{stack.pop();}.