一、 直方图中的最大矩形

题目

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

解法

解法一 暴力法

我们知道，两个柱子间矩形的高由它们之间最矮的柱子决定，因此可以暴力遍历数组，考虑所有两两柱子之间形成的矩形面积，该矩形的高为它们之间最矮柱子的高度，宽为它们之间的距离，这样可以找到所要求的最大面积的矩形。
这样做的时间复杂度是O(N3)，空间复杂度是O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int largestRectangleArea(int[] heights)
{
	int maxArea = 0;
	for(int i = 0; i < heights.length; i++)
	{
		for(int j = i; j < heights.length; j++)
		{
			int minHeight = Integer.MAX_VALUE;
			for(int k = i; k <= j; k++)
			{
				minHeight = Math.min(minHeight, heights[k]);
			}
			maxArea = Math.max(maxArea, (j - i + 1) * minHeight);
		}
	}
	return maxArea;
}

解法二 优化暴力法

我们用前一对柱子的之间的最低高度与当前柱子的高度进行比较，求出当前一对柱子之间的最低高度，宽依然是当前这对柱子之间的距离。
代码如下：
则时间复杂度变为O(N2)，空间复杂度依然是O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int largestRectangleArea(int[] heights)
{
	int maxArea = 0;
	for(int i = 0; i < heights.length; i++)
	{
		int minHeight = Integer.MAX_VALUE;			
		for(int j = i; j < heights.length; j++)
		{
			minHeight = Math.min(minHeight, heights[j]);
			maxArea = Math.max(maxArea, (j - i + 1) * minHeight);
		}
	}
	return maxArea;
}

解法三 分治

首先分解问题，找最大面积的矩形的方法可以如下：

  1. 确定了最矮柱子以后，矩形的宽尽可能往两边延伸。
  2. 在最矮柱子左边的最大面积矩形（子问题），找到左边的最矮的柱子，计算面积
  3. 在最矮柱子右边的最大面积矩形（子问题）。
    代码如下：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    public int largestRectangleArea(int[] heights)
    {
    	return calculateArea(heights, 0, heights.length - 1);
    }

    public int calculateArea(int[] heights, int leftIndex, int rightIndex)
    {
    	if(leftIndex > rightIndex)
    	{
    		return 0;
    	}
    	int minHeightIndex = leftIndex;
    	for(int i = leftIndex; i <= rightIndex; i++)
    	{
    		if(heights[i] < heights[minHeight])
    		{
    			minHeightIndex = i;
    		}		
    	}
    	int currentArea = heights[minHeightIndex] * (rightIndex - leftIndex + 1);
    	int leftArea = calculateArea(heights, leftIndex, minHeightIndex - 1);
    	int rightArea = calculateArea(heights, minHeightIndex + 1, rightIndex);
    	return Math.max(currentArea, Math.max(leftArea, rightArea));
    }

时间复杂度：

  • 平均开销：O(NlogN)
  • 最坏情况：O(N2)，如果数组中的数字是有序的，分治算法将没有任何优化效果。
    空间复杂度：O(N)，最坏情况下递归需要O(n)的空间。

解法四 优化分治

用线段树代替遍历来找到区间最小值

解法五 栈（最优）

假设数组元素是升序的，那么求最大矩形的面积思路可以如下：先看最右边即最高的元素，其能形成的最大矩形就是它本身，面积为它的高度乘以1；然后再看倒数第二高的元素，它能形成的最大矩形的高是它的高度，宽为2；然后一直往左，最左侧最低的元素能形成的最大矩形的高度是它的高度，宽为数组的长度，也就是最高的元素的下标 + 1-当前元素下标，（这里的+1是因为矩形宽度为1，假设序号对应的是柱子的左下角）

那么我们的目标就出来了，求以当前柱子为高能形成的最大矩形的面积，关键就是找宽：矩形的左侧就是该柱子左侧第一个比当前柱子要低的柱子，矩形的右侧就是该柱子右侧第一个比当前柱子要低的柱子。

那么，我们可以维护一个单调栈，这个栈存储的是数组的下标。我们的目的就是维护这个单调栈，使得栈内元素（数组下标）对应的柱子高度是升序的。
从左到右开始遍历数组，当遍历到第i个元素时：

  1. 如果栈为空或者当前柱子i的高度比前一个柱子的高度要高，则把当前柱子的下标push到栈顶
  2. 如果栈不为空且当前柱子i的高度比前一个柱子（栈顶柱子，即为A）高度要低，则柱子A无法与当前柱子i以及当前柱子i以后的柱子形成矩形了，因此弹出柱子A，并计算以柱子A为高的最大矩形的面积，直到栈顶元素对应的柱子高度比当前柱子i的高度要低为止。
    • 高度：柱子A的高度
    • 矩形右侧边沿：当前元素的下标i，因为单调栈的性质，第i个柱子就是柱子A右侧第一个比A低的柱子
    • 矩形左侧边沿：第一个比柱子A低的柱子，即栈中紧邻A的柱子，当A出栈后，左边沿就是栈顶的元素，并且是该柱子的右侧，因此要+1 （这里设i序号对应柱子的左下角）
    • 在求左边沿时要注意，如果A出栈后栈为空，那么说明A左侧没有比它更低的柱子了，因此左边沿可以到0
    • maxArea = Math.max(maxArea, heights[i] * stack.isEmpty() ? i : i - (stack.peek() + 1))

此时遍历完数组后，就构建好了我们的单调栈，当这个单调栈不为空时，我们将栈中元素全部弹出栈，开始从右侧向左侧开始计算矩形面积，最终得到整体上的最大矩形面积。

代码如下：

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
public int largestRectangleArea(int[] heights)
{
	if (heights.length == 0)
    {
        return 0;
    }
	Stack<Integer> rectangleIndexStack = new Stack<>();
	int maxArea = 0;
	int index = 0;
	while(index < heights.length)
	{
		if(rectangleIndexStack.isEmpty || heights[rectangleIndexStack.peek()] <= heights[index])
		{
			rectangleIndexStack.push(index++);
		}
		else
		{
			int currentTopHeight = heights[rectangleIndexStack.pop()];
			int width = rectangleIndexStack.isEmpty() ? index : index - rectangleIndexStack.peek() - 1;
			maxArea = Math.max(maxArea, currentTopHeight * width);
		}
	}

	while(!stack.isEmpty())
	{
		int currentTopHeight = heights[rectangleIndexStack.pop()];
	    int width = rectangleIndexStack.isEmpty() ? index : index - rectangleIndexStack.peek() - 1;
        maxArea = Math.max(maxArea, currentTopHeight * width);
	}
	return maxArea;
}

这种利用栈的方法的时间复杂度是O(N),N个数组元素会被压栈、出栈各一次；空间复杂度是O(N)，用来存放栈中的元素。

直方图问题参考资料

[1]柱状图中最大的矩形
[2]算法题：直方图和0-1矩阵中最大矩形
[3]84. 柱状图中最大的矩形/C++
[4]Largest Rectangular Area in a Histogram | Set 2

解决了直方图的问题之后，我们进入到第二题。

二、 0-1 子矩阵问题

题目

给定一个矩形区域，每一个位置上都是1或0，求该矩阵中每一个位置上都是1的最大子矩形区域中的1的个数。

示例

矩阵如下：
1 0 1 1
1 1 1 1
1 1 1 0

输出：6

分析

我们可以将这个问题转化为已知的第一个问题。思路就是，将矩阵进行压缩，第一行不变，从第二行开始，将第i行与第i-1、第i-2、…、第1行进行合并，压缩成一个一维的数组，如果第i行的当前元素为0，则合并后的数组对应位置的元素为0；如果第i行的当前元素不为0，则合并后数组对应位置的元素变为上一行对应元素+1。这样做的目的是，找出当前行的正上方有多少个连续的1，构造成一个以当前行为底直方图，高就是截止到该行位置，这一列上方连续1的个数，然后调用上面问题一的方法计算最大的矩形面积。遍历完所有行之后，就可以找到最大的全是1的子矩阵了。

代码实现

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public int maxSubRectangleSize(int[][] matrix)
{
	if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
	{
        throw new IllegalArgumentException();
	}
	int maxArea = 0;
	int[] heights = new int[matrix[0].length];
    int row = matrix.length;
    int column = matrix[0].length;
	for(int i = 0; i < row; i++)
	{
		for(int j = 0; j < column; j++)
		{
			heights[j] = matrix[i][j] == 0 ? 0 : heights[j] + 1;
		}
		maxArea = Math.max(maxArea, largestRectangleArea(heights));
	}
	return maxArea;
}

public int largestRectangleArea(int[] heights)
{
	if (heights.length == 0)
    {
        return 0;
    }
    Stack<Integer> rectangleIndexStack = new Stack<>();
    int maxArea = 0;
    int index = 0;
    while (index < heights.length)
    {
        if (rectangleIndexStack.isEmpty() || heights[rectangleIndexStack.peek()] <= heights[index])
        {
            rectangleIndexStack.push(index++);
        }
        else
        {
            int topValue = heights[rectangleIndexStack.pop()];
            int width = rectangleIndexStack.isEmpty() ? index : index - rectangleIndexStack.peek() - 1;
            maxArea = Math.max(maxArea, topValue * width);
        }
    }
    while (!rectangleIndexStack.isEmpty())
    {
        int topValue = heights[rectangleIndexStack.pop()];
        int width = rectangleIndexStack.isEmpty() ? index : index - rectangleIndexStack.peek() - 1;
        maxArea = Math.max(maxArea, topValue * width);
    }
    return maxArea;
}

参考资料

[1]算法题：直方图和0-1矩阵中最大矩形
[2]Maximum size rectangle binary sub-matrix with all 1s