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.
这道题可以有两个解法。
解法一是穷举法，对于直方图的每一个右边界，穷举所有的左边界。将面积最大的那个值记录下来。时间复杂度为O(n^2). 单纯的穷举在LeetCode上面过大集合时会超时。可以通过选择合适的右边界，做一个剪枝(Pruning)。观察发现当height[k] >= height[k - 1]时，无论左边界是什么值，选择height[k]总会比选择height[k - 1]所形成的面积大。因此，在选择右边界的时候，首先找到一个height[k] < height[k - 1]的k，然后取k - 1作为右边界，穷举所有左边界，找最大面积。
public int largestRectangleArea(int[] height) { // Note: The Solution object is instantiated only once and is reused by each test case. int area = 0; for(int i = 0; i < height.length; i++) { for(int k = i+1; k < height.length ; k++){ if(height[k] < height[k-1]){ i=k-1; break;// sytax error was here!! break the loop when find K } else{ i = k; } } int lowest = height[i]; for(int j = i; j>=0 ; j--){ if(height[j] < lowest){ lowest = height[j]; } int curArrea = (i-j+1)*lowest; if(curArrea > area){ area = curArrea; } } } return area; }
// O(n) using two stacks public int largestRectangleArea(int[] height) { // Start typing your Java solution below // DO NOT write main() function int area = 0; java.util.Stack<Integer> heightStack = new java.util.Stack<Integer>(); java.util.Stack<Integer> indexStack = new java.util.Stack<Integer>(); for (int i = 0; i < height.length; i++) { if (heightStack.empty() || heightStack.peek() <= height[i]) { heightStack.push(height[i]); indexStack.push(i); } else if (heightStack.peek() > height[i]) { int j = 0; while (!heightStack.empty() && heightStack.peek() > height[i]) { j = indexStack.pop(); int currArea = (i - j) * heightStack.pop(); if (currArea > area) { area = currArea; } } heightStack.push(height[i]); indexStack.push(j); } } while (!heightStack.empty()) { int currArea = (height.length - indexStack.pop()) * heightStack.pop(); if (currArea > area) { area = currArea; } } return area; }
在网上发现另外一个使用一个栈的O(n)解法，代码非常简洁，栈内存储的是高度递增的下标。对于每一个直方图高度，分两种情况。1：当栈空或者当前高度大于栈顶下标所指示的高度时，当前下标入栈。否则，2：当前栈顶出栈，并且用这个下标所指示的高度计算面积。而这个方法为什么只需要一个栈呢？因为当第二种情况时，for循环的循环下标回退，也就让下一次for循环比较当前高度与新的栈顶下标所指示的高度，注意此时的栈顶已经改变由于之前的出栈。
// 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; }