Leetcode 84 直方图中的最大矩形

Question:

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 heights = [2,1,5,6,2,3],
return 10.

Coding:

本题的最容易想到的解决方法是使用暴力枚举法，对每一个矩阵进行遍历，然后从以当前矩阵为结束的矩阵中找出最大的那个，作为局部最大值。遍历完所有矩阵，所存的最大的矩阵即为解答。该方法的时间复杂度为O(N^2)，正常提交无法通过LeetCode的测试用例 (Run Time Error)。

这个问题常规的解法时间复杂度为O(N)，使用栈的特性，只要进行一遍遍历就可找出最大值。但是因为解决思路比较复杂，怕以后review代码的时候难以理解，遂记录，具体的解决思路从Youtube视频中学到，视频链接附在文末。

本题的关键在于找出以下三种情况：

  • 情况1：

    如上图所示，两个矩阵相同时，最大矩阵其实就是两个矩阵的面积，此使我们只要存储前一矩阵的下标以记录这一高度的开始值。

  • 情况2：

    如上图所示，当前一个矩阵C比后一个矩阵D面积大时，C已经结束了，因为它不可能以本身的高和后面的矩阵构成更大的矩阵。因此我们不需要再存储它的信息。这时我们需要记录它能构成的最大面积——即它的下标与当前下标差（表明以这样的高度持续了多少个下标）乘它的高度。而接下来的那个小矩阵D，其实是从前一个矩阵C的内部开始的。这句话很重要，也是后面栈操作的关键。

  • 情况3

    如上图所示，当前一个矩阵E比后一个矩阵F面积小，则E还未结束（还可能以当前E的高和后面的矩阵结合生成新的大矩阵），因此它们的高度都要存储。

经过以上分析可以看出我们实际需要两个栈来进行存储，一个栈存储矩阵高度，一个栈存储矩阵下标。

我们用以下的例子进行分析：


在上图中有5个矩阵，高度分别标在矩阵内部。

  • Step 1

    此时第一个矩阵高度为1，栈为空，我们将其下标推入p栈，高度推入h栈。

  • Step 2

    第二个矩阵高度大于第一个矩阵，根据情况3，我们直接将其下标和高度分别推入栈中。

  • Step 3

    第三个矩阵高度小于第二个矩阵，根据情况2，我们将矩阵2弹出，计算3*(2-1) = 3并记录，然后将矩阵3放入栈中。此时，注意上面我们加粗的那句话，因为矩阵3是从矩阵2的内部开始的，因此下标保持不变。

  • Step 4

    这一步进行了很多操作，我们一个个来。首先是矩阵4的高度比矩阵3小，我们将矩阵3弹出，并计算2*(3-1) = 4，然后由于要放入栈中的矩阵4高度和当前栈中的矩阵2相同，我们放弃存入矩阵4并弹出矩阵3的位置记录。

  • Step 5

    接下来存入的矩阵5高度比栈顶矩阵高，因此根据情况3，我们继续压入矩阵和位置。

  • Step 6

    此时已经没有矩阵需要存入，我们要依次处理栈中剩余矩阵。首先把当前的矩阵5和其位置弹出，并计算2*(5-4)​，其中5表示后一个下标位置。

  • Step 7

    继续弹出矩阵1和其位置，并计算1*(5-0)。

最后，我们发现，最大的面积为5。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int largestRectangleArea(int[] heights) {
		int index = 0, maxarea = 0;
		Stack<Integer> S_h = new Stack<>();
		Stack<Integer> S_p = new Stack<>();
		if (heights.length == 0) return 0;
		
		S_h.push(heights[0]);
		S_p.push(0);
		index++;
		while (!S_h.isEmpty()) {
			if (index == heights.length) {  
				maxarea = Math.max(maxarea, S_h.pop() * (index - S_p.pop()));
			} else {
				if (heights[index] > S_h.peek()) {  /* 情况3 */
					S_h.push(heights[index]);
					S_p.push(index);
				} else if (heights[index] < S_h.peek()) {  /* 情况2 */
					maxarea = Math.max(maxarea, S_h.pop() * (index - S_p.peek()));
					if (S_h.isEmpty() || heights[index] > S_h.peek()) {
						S_h.push(heights[index]);
					} else if (heights[index] == S_h.peek()) {
				    	S_p.pop();
				    } else if (heights[index] < S_h.peek()) {
				    	index--;
				    	S_p.pop();
				    }
				}
				index++;
			}
		}
		return maxarea;
	}

源代码文件可参见我的Github: Solution for Largest Rectangle in Histogram.java

Reference: