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.

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.

//============================================================================
// Name        : MaxRectagle.java
// Author      : GaoTong
// Date        : 2014/9/5
//============================================================================
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;
}
}
}

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;
}

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();}.