Fork me on GitHub

算法-直方图中的最大矩形

发表于 | 分类于 | 阅读次数
面试算法之----求直方图最大矩形（摘自数据结构与算法经典问题解析 95 页问题 24）

直方图中最大矩形（(Largest Rectangle in Histogram)）

问题：直方图是由排列在同一基线上的一系列矩形组成的多边形。为了简单起见，假设这些矩形的宽度相等但高度可能不同。例如，下图1给出了一个直方图，其中各个矩形的高度为3、2、5、6、1、4、4，宽度为标准1单位。当给定了一个保存所有矩形高度的数组时，如何找到其中最大的矩形。对于给定的例子，最大矩形如图2阴影部分所示：
这里写图片描述

  • 时间复杂度：O（n） （高效率）
  • 空间复杂度：O（n） （栈开销）

这个问题有多种解法，包含枚举、动态规划、分治等等。
这儿我们采用一种巧妙的方法，使用堆栈，将复杂度降到最低。

算法思想：

1、新建一个空栈，将 A[1] 压入栈中，此时 A[1] 位于栈顶。

2、A[i] 与栈顶元素比较。如果A[i] 大，那么将其入栈。如果两者相等，跳过，继续下一个元素。

  • 如果A[i]小于当前栈顶元素，说明已经找到第一个位于栈顶右边的比它小的值（此时这个较小的元素还未入栈），在它的左边（在栈内就是它脚下的元素）即为第一个左边比它小的值。此时需要这样做：
- 以栈顶元素为最小高度计算最大矩形面积，并更新现在的最大面积，宽度为左边界到右边界。

- 弹出栈顶元素。

- 重复第2步。

3.扫描完后，一般情况下会剩下一个单调递增的堆栈，那么一个一个出栈计算面积就可以了。左边依旧还是栈顶下面那个值，右边这个时候就不存在了，最后一个栈状态的栈顶即为右边界。

就拿上面的输入为例：[3、2、5、6、1、4、4]

首先：记左边界为字母L，右边界为字母R，图中红色框为最新最大面积。

这里写图片描述

1、 堆栈[ ]，开始扫描i从0到6；

2、 i=0，因为堆栈为空，把3入栈【此时堆栈为[0]】

3、 i=1，因为a[i] =2 < a[top] = a[0] =3，所以这个时候0出栈，并且计算a[0]作为矩形最小高度的面积，因为堆栈已空，所以左边界L就是0，右边界R就是i−1=0；所以最大面积就是a[0]×(R−L+1)=3;【此时堆栈为[ ]】然后再把i=1入栈。【此时堆栈[1]】，如上图。

这里写图片描述

4、 i=2，因为a[i] =5 > a[top] = a[1] =2，所以i=2入栈。【此时堆栈[1,2]】

5、 i=3，因为a[i] =6 > a[top] = a[2] =5，所以i=3入栈。【此时堆栈[1,2,3]】

6、 i=4，因为a[i] =1 < a[top] = a[3] =6，所以3要出栈，并且计算a[3]=6作为矩形最小高度的面积，左边就是栈顶下一个值加1，L=2+1=3，右边R=i−1=3，所以最大面积就是a[3]×(R−L+1)=6 ;【此时堆栈[1,2]】。如上图。

这里写图片描述

此时a[i] =1 < a[top] = a[2] =5，所以2也要出栈，并且计算a[2]=5作为矩形最小高度的面积，左边就是栈顶下一个值加1，L=1+1=2，右边R=i−1=3，所以最大面积就是a[2]×(R−L+1)=10 ;【此时堆栈[1]】。如上图 。

这里写图片描述

再此时a[i] =1 < a[top] = a[1] =2，所以1也要出栈，并且计算a[1]=2作为矩形最小高度的面积，因为栈已空，则左边界为0，右边界R=i−1=3，所以最大面积就是a[1]×(R−L+1)=8 ，小于10，取10 ; 最后i=4入栈。【此时堆栈[4]】。如上图。

7、 i=5，因为a[i] =4 > a[top] = a[4] =1，所以i=5入栈。【此时堆栈[4,5]】

8、 i=6，因为a[i] =4 = a[top] = a[4] =1，跳过。【此时堆栈[4,5]】

9、 i=7，扫描完毕了，此时a[4]，a[5]，a[6]必然单调增。然后再一个个出栈。

这里写图片描述

10、top=5出栈，计算面积，L=4+1=5,右边没值，相当于右边还有一个a[i=7]=0的矩形，那么R=7−1=6，所以面积就是a[5]×(R−L+1)=8。【此时堆栈[4]】。如上图。

这里写图片描述

11、top=4出栈，计算面积，栈空，左边为0，右边没值，相当于右边还有一个a[i=7]=0的矩形，那么R=7−1=6，所以面积就是a[4]×(R−L+1)=7。【此时堆栈[ ]】。如上图。

12.计算完毕；

算法如下（java）：

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
public StackItem(int height, int index) {
			// TODO Auto-generated constructor stub
			this.height=height;
			this.index=index;
		}
		public int height;
		public int index;
		}
		public int MaxRecttangleArea(int A[],int n){
		int maxRean=0;
		if(null==A || A.length<=0){
			return maxRean;
		}
		Stack<StackItem> S=new Stack<StackItem>();
		//先往栈中压入一个起始元素，为了进入后面的while循环
		S.push(new StackItem(Integer.MIN_VALUE,-1)); 
		//这儿循环A.length次，让元素全部出栈
		for(int i=0;i<n;i++){  
			StackItem cur=new StackItem((i<n?A[i]:Integer.MIN_VALUE),i);
			//lastElement 为栈顶
			if(cur.height>S.lastElement().height){ 
				S.push(cur);
				continue;
			}
			while(S.size()>0){
				StackItem prev=S.lastElement();
				int area=(i-prev.index)*prev.height;
				if(area>maxRean){
					maxRean=area;
				}
				prev.height=cur.height;
				if(prev.height>S.get(S.size()-2).height){
					break;
				}
				S.pop();
			}
		}
		return maxRean;
	}

我们测试一下时间：

1
2
3
4
5
6
7
8
public static void main(String[] arg){
		int[] A=new int[]{3,2,5,6,1,4,4};
		MaxRectangleArea clazz=new MaxRectangleArea();
		long time=System.nanoTime();
		System.out.println(clazz.MaxRecttangleArea(A, 7)+"");
		 long estimatedTime = System.nanoTime() - time;
		System.out.println(estimatedTime);
	}

打印结果如下：

1
2
10
1169687

总耗时1ms。

csdn地址：http://blog.csdn.net/u012534831
github地址：https://github.com/qht1003077897
个人博客地址：https://qht1003077897.github.io/
QQ：1003077897