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.

基本思路：

用栈来存储“height”和“index”，保证栈中的高度是递增的，扫描的时候会出现以下三种情况：

1.height[current]>height[stack.pop()]

此时入栈height和index

2.height[current]<height[stack.pop()]

此时计算面积，出栈，更新最大面积。直到遇到height[current]>height[stack.pop()]

3.height[current]==height[stack.pop()]

	public int largestRectangleArea(int[] height)
	{
		if (height == null || height.length == 0)
			return 0;

		int maxArea = 0;
		Stack<Integer> stackHeight = new Stack<Integer>();
		Stack<Integer> stackIndex = new Stack<Integer>();

		for (int i = 0; i < height.length; i++)
		{
			// case 1
			if (stackHeight.isEmpty() || height[i] > stackHeight.peek())
			{
				stackHeight.push(height[i]);
				stackIndex.push(i);
			}
			else if (height[i] < stackHeight.peek())
			{
				// case 3
				int lastIndex = 0;
				while (stackHeight.isEmpty() == false
						&& height[i] < stackHeight.peek())
				{
					lastIndex = stackIndex.pop();
					int tempArea = stackHeight.pop() * (i - lastIndex);
					if (maxArea < tempArea)
					{
						maxArea = tempArea;
					}
				}
				//添加当前height和lastIndex进栈，至于为什么添加lastIndex，就是防止当前图形和前面的递增图形构成的面积比前面递增图形构成的面积大
				stackHeight.push(height[i]);
				stackIndex.push(lastIndex);
			}
		}

		//处理栈中剩余元素
		while (stackHeight.isEmpty() == false)
		{
			int tempArea = stackHeight.pop()
					* (height.length - stackIndex.pop());
			if (tempArea > maxArea)
			{
				maxArea = tempArea;
			}
		}
		return maxArea;
	}

Largest Rectangle in Histogram,布布扣,bubuko.com

Largest Rectangle in Histogram

原文：http://blog.csdn.net/cow__sky/article/details/21037023