首先回顾一道以前career cup上做过的题，
Container With Most Water
Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container.
最快的解法：
从两边向中间移动，每次移动比较短的那个板。这样的话唯一的变量就是width了。记录下装水量并和当前最大相比较，直到两块板相遇为止。greedy算法。
证明：类似于数学归纳法，我们从width最大开始，对于当前宽度，继续往前移长板不可能产生更大的面积，所以对于短板来说，以他为边界的最大值已经evaluate过了（另外一边边界已经全都evaluate过），所以我们将短板向前移动，直到宽度为0.
接下来进入正题
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.
最brute force的方法，扫描所有的i，j为左右边的组合，找出最大面积，计算以i，j为边的长方形最大面积的方法就是找到i，j中间最小的那一点，乘以宽度，然后跟最大值比较。当然这种方法肯定不是最优的。
public class Solution {
public int largestRectangleArea(int[] height) {
if (height.length == 0)
return 0;
int maxA = 0;
//calculate rect area between j and i (exclusive)
for (int i = 1; i = 0; j--)
{
minH = Math.min(minH, height[j]);
int area = minH * (i - j);
maxA = Math.max(area, maxA);
}
}
return maxA;
}
}
加入剪枝，因为只要是右边增加的histogram在一直增高，总面积总是在增加的。（换种说法就是左边界为j，右边界i如果属于一段递增数列，rectangle的最大值肯定是i为递增数列最高点时候的面积），那么他的所以我们只需要比较那些i = 递增峰值的rectangle的面积，这样可以剪去很多分支，但是runtime还是O(n^2).
public class Solution {
public int largestRectangleArea(int[] height) {
if (height.length == 0)
return 0;
int maxA = 0;
//calculate rect area between j and i (exclusive)
int start = 1;
while(start = height[start-1])
{
start++;
if (start == height.length)
break;
}
}
int minH = height[start-1];
for (int j = start-1; j >= 0; j--)
{
minH = Math.min(minH, height[j]);
int area = minH * (start - j);
maxA = Math.max(area, maxA);
}
start++;
}
return maxA;
}
}
最后是一种线性复杂度的方法， 利用stack：There was a mistake in the link below. although the algorithm was correct, the pic was not correct (see the comment below the post)
简单的算法是这样的。用一个stack储存index
第一个数先push入栈，如果数一直递增的话，那么就一直push入栈，直到数开始减小为止。所以先计算所有这些递增直方中比最后一个直方高的所有直方能围成的面积最大值并将它们弹出stack，然后再继续，直到下一个又开始减小又继续弹出，最后到index结束为止。最后将stack清空计算最大值为止。具体原理请看上面的解释，其实相当于把弹出的直方用和递减的那个直方高度相同的直方代替。
public class Solution {
public int largestRectangleArea(int[] height) {
Stack<Integer> s = new Stack<Integer>();
int maxArea = 0;
for (int i = 0; i < height.length; i++)
{
if(s.isEmpty() || height[i] >= height[s.peek()])
{
s.push(i);
}
else
{
int t = s.pop();
if (s.isEmpty()) // go all the way to 0
maxArea = Math.max(maxArea, height[t] * i);
else // go to the last smallest element
maxArea = Math.max(maxArea, height[t] * (i - s.peek() - 1));
i--;// no need to ++ if pops from stack, compensate the ++ in the for loop
}
}
while(!s.isEmpty())// when all the elements has been scaned, pop everything left in the stack
{
int t = s.pop();
if (s.isEmpty()) // go all the way to 0
maxArea = Math.max(maxArea, height[t] * (height.length));
else // go to the last smallest element
maxArea = Math.max(maxArea, height[t] * (height.length - s.peek() - 1));
}
return maxArea;
}
}
Second Submission: put in a 0 element to make code looks cleaner, remember to use the i, s.peek() to get the current width and the temp(s.pop) to get current height.
Forgot to use height[area.peek()], which is the height of the bar to do the comparison. Third submission.
public class Solution {
public int largestRectangleArea(int[] height) {
Stack<Integer> area = new Stack<Integer>();
int maxArea = 0;
for (int i = 0; i < height.length; i++) {
if (area.isEmpty() || height[i] >= height[area.peek()]) {
area.push(i);
}
else {
while(!area.isEmpty() && height[i] < height[area.peek()]){
int tmp = area.pop();
maxArea = Math.max(maxArea, height[tmp] * (area.isEmpty()? i : i - area.peek() - 1));
}
area.push(i);
}
}
//pop everything out of the stack
while(!area.isEmpty()){
int tmp = area.pop();
maxArea = Math.max(maxArea, height[tmp] * (area.isEmpty()? height.length : height.length - area.peek()-1));
}
return maxArea;
}
}
