[LeetCode]Largest Rectangle in Histogram

又是一道题可以引出一类题的题目，首先brute-force的解法是对于每一个坐标向两边扩展，找出最大值，时间复杂度是O(n^2)。优化的话，我们首先考虑divide and conquer的做法，具体做法是二分，找出左边的最大值，右边的最大值和穿过左边和右边的最大值。算法的复杂度取决于最后一步，也就是寻找穿过左边和右边的最大值的时间复杂度。我们下面详细讲解这一步可以在O(n)时间内完成，所以总的时间复杂度是O(n log n)，空间复杂度是O(n)。
首先确定的是findcross找的结果是要穿过两个部分的最大值，所以两边至少要有一个直方，假设位于mid和mid + 1的直方的较小的值为height，那么最后找到的最大矩形的高度肯定是小于等于height的，因为我们找的是cross。所以最大值，就是左右两端小于height的直方为高度围成的所有矩形中的最大值，注意不是所有的小于height的我们都会考虑，我们考虑的是从中间分别像两边扩散的递减序列，已左边为例，也就是从中间向左边走第一个小于height的值height1，继续往右边走第一个小于height1的值，height2，以此类推，对于右边来说也是一样的。以下图为例：

我们依次check的矩形是：

• 以直方6高度围成的最大矩形
• 以直方8高度围成的最大矩形
• 以直方9高度围成的最大矩形
• 以直方5高度围成的最大矩形
• 以直方2高度围成的最大矩形
• 以直方12高度围成的最大矩形

注意虽然直方4的高度也小于height，但我们不会check以他为高度的矩形，因为他不在我们之前所说的序列当中。当我们找到两边的序列之后，我们是按照高度递减的次序依次check的能围成的最大矩形，定义两个变量，左边的为i，指向5，右边的为j，指向8：

• 首先我们找到两边第一个小于height的坐标，此时i指向5，j指向8
• 计算以直方6为高度围城的最大矩形
• 因为直方8的高度大于直方5的高度，所以已直方8为高度的矩形的左边界就是5的前一个直方，所以我们移动j来找右边界，找到比直方8高度小的第一个直方，此时j指向9，i指向5
• 计算以直方8为高度围成的最大矩形，然后根据之前的策略移动j到12
• 计算以直方9为高度围成的最大矩形，然后根据之前的策略移动i到2
• 计算以直方5为高度围成的最大矩形，然后根据之前的策略移动i到0(超出边界)
• 计算以直方2为高度围成的最大矩形，然后根据之前的策略移动j到13(超出边界)
• 计算以直方12为高度围成的最大矩形，结束

代码如下：

	public class Solution {
	public int largestRectangleArea(int[] height) {
	if (height == null)
	return 0;
	int len = height.length;
	return getArea(height, 0, len - 1);
	}
	private int getArea(int[] height, int lo, int hi) {
	if (lo > hi)
	return 0;
	if (lo == hi)
	return height[lo];
	int mid = lo + (hi - lo) / 2;
	int left = getArea(height, lo, mid);
	int right = getArea(height, mid + 1, hi);
	int cross = getCross(height, mid, lo, hi);
	return max(left, right, cross);
	}
	private int getCross(int[] height, int mid, int lo, int hi) {
	int i = mid - 1, j = mid + 2, hei = height[mid] <= height[mid + 1]? height[mid]: height[mid + 1];
	//find the first index whose height is lower than hei, both let and right
	while (i >= lo && height[i] >= hei)
	i--;
	while (j <= hi && height[j] >= hei)
	j++;
	int max = hei * (j - i - 1);
	//find the next index whose height is the largest height lower than hei
	while (i >= lo && j <= hi) {
	if (height[i] >= height[j]) {
	hei = height[i];
	while (i >= lo && height[i] >= hei)
	i--;
	} else {
	hei = height[j];
	while (j <= hi && height[j] >= hei)
	j++;
	}
	int area = hei * (j - i - 1);
	max = area > max? area: max;
	}
	//deal with the rest
	while (i >= lo) {
	hei = height[i];
	while (i >= lo && height[i] >= hei)
	i--;
	int area = hei * (j - i - 1);
	max = area > max? area: max;
	}
	while (j <= hi) {
	hei = height[j];
	while (j <= hi && height[j] >= hei)
	j++;
	int area = hei * (j - i - 1);
	max = area > max? area: max;
	}
	return max;
	}
	private int max(int a, int b, int c) {
	int max = a >= b? a: b;
	return max >= c? max: c;
	}
	}

view raw largest histogram v-1.java hosted with ❤ by GitHub

然后还有一个很牛逼的维护递增栈的方法，时间复杂度是O(n)，空间复杂度是O(n)。大体思想是，栈里面的永远是递增的直方，碰到一个新的直方，如果大于栈顶的直方，压入栈，否则，如果栈顶的元素大于它，一直弹出并计算以弹出直方为高度的能围成的最大矩形，直到栈顶元素小于他或者栈为空，然后压入栈，这种方法可以保证我们弹出元素的时候能计算以弹出直方为高度的能围成的最大矩形，因为右边界是我们要压入的元素，由于是递增栈，左边界是peek的左边加一的直方。具体思想可以check这里。

代码如下：

	public class Solution {
	public int largestRectangleArea(int[] height) {
	if (height == null)
	return 0;
	int len = height.length;
	int max = 0;
	Stack<Integer> stack = new Stack<Integer>();
	for (int i = 0; i <= len; i++) {
	int curr = i == len? 0: height[i];
	while (!stack.isEmpty() && height[stack.peek()] >= curr) {
	int hei = height[stack.pop()];
	int width = stack.isEmpty()? i: i - stack.peek() - 1;
	int area = hei * width;
	max = area > max? area: max;
	}
	stack.push(i);
	}
	return max;
	}
	}

view raw largest histogram v-2.java hosted with ❤ by GitHub