二维矩阵中的最大矩形面积–java实现

二维矩阵中的最大矩形面积–java实现

一、原题:

给你一个二维矩阵,权值为False和True,找到一个最大的矩形,使得里面的值全部为True,输出它的面积。

样例:

给你一个矩阵如下:

[
  [1, 1, 0, 0, 1],
  [0, 1, 0, 0, 1],
  [0, 0, 1, 1, 1],
  [0, 0, 1, 1, 1],
  [0, 0, 0, 0, 1]
]

输出6

 

二、解题思路:

1、首先,第一种解题方法,也就是最简单最容易想到的方法,就是暴力遍历二维数组中的每一个元素,然后求出该元素所在区域的最大矩形的面积,但是这种方法的时间复杂度太高,不建议这样子做。

2、接下来,介绍另外一种方法: Histogram法

根据下图,可以看出本题可以转化为Largest Rectangle in Histogram来做。

二维矩阵中的最大矩形面积--java实现

看到这里,可能有些人会不明白什么是Histogram法,那么,在贴出本题的解决代码之前,我们先介绍一下什么是Histogram法。

 

三、Histogram法:

本部分参考博客:https://blog.csdn.net/hopeztm/article/details/7868581

1、题目大意:

给出一个柱形统计图(histogram), 它的每个项目的宽度是1, 高度和具体问题有关。 现在编程求出在这个柱形图中的最大面积的长方形。

例如:

7 2 1 4 5 1 3 3

7表示柱形图有7个数据,分别是 2 1 4 5 1 3 3, 对应的柱形图如下,最后求出来的面积最大的图如右图所示。

二维矩阵中的最大矩形面积--java实现

2、分析:

如果采用枚举的方式,如果当前我们枚举项是 i = 0, 即 height = 2时, 我们用另外两个变量 j 和k 向左和向右两个方向搜素,分别找到第一个小于当前height的下标,这样我们就可以算出用 i 项作为高度长方形的面积了。

我们假设 -1位置,和最右高度都是无穷小。

例如:

i = 0, j = -1, k = 1, 最后的面积是 (k – j – 1) * height = 2

i = 1, j = -1, k = 7, 最后面积是( k – j – 1) * height = 7;

i = 3, j = 2, k = 5 面积是 ( k – j – 1) * height = 8 

枚举出所有的长方形的同时,然后得到最后的面积。

不过这样的程序的时间复杂度是 O(n^2)

3、我们如何能仅仅做一次,就求出这个面积呢?

观察:

当我们扫扫描到第一个高度 H1 = 2的时候,我可以标记它的起始位置1, 因为我们还不知道它将向右扩展到什么地方,所以继续扫面。

当遇到第二项 H2 = 1, 因为这项比之前的小,我们知道,用H1做高度的长方形结束了,算出它的面积。

同时这个时候,我们多了一个高度H2,用它做长方形高度的长方形起始位置应该是在哪里呢? 因为H1的高度比H2要高,所以这个起始位置自然是H1所在的位置。

 

为了模拟上面的过程,我们引入单调栈,并使用Node对象用于保存的每一项数据:

//节点
class Node{
	//矩形高度
	Integer height;
	//矩形坐标
	Integer startIndex;
	
	Node(Integer height,Integer startIndex){
		this.height=height;
		this.startIndex=startIndex;
	}
	
	public Integer getHeight() {
		return height;
	}
	public void setHeight(Integer height) {
		this.height = height;
	}
	public Integer getStartIndex() {
		return startIndex;
	}
	public void setStartIndex(Integer startIndex) {
		this.startIndex = startIndex;
	}
}

然后我们按照高度来组织成单调栈。我们来看一下它是如何工作的。

为了不用考虑堆栈为空的情况,我们用插入栈底 一个高度(0, 0)的项。

数据:2 1 4 5 1 3 3 

这样初始化:

(0,0)

   i=1:

当扫描到(2,1)时候,因为高度2 大于栈顶,插入

(0,0),(2,1)

   i=2:

当扫描到1的时候,因为1小于栈顶高度2, 我们认为栈顶的那个高度应不能再向右扩展了,所以我们将它弹出,这个时候扫描到   i = 2;

高度是 (i – (H1.startIndex)) * H1.height = 2;

我们得到一个面积是2的长方形。

同时我们发现高度是1的当前高度,可以扩展到 H1所在的下标,所以我们插入( 1, 1) 堆栈变成

(0, 0), (1, 1) 因为(2, 1)已经不能向右伸展了,已经被弹出了。

  i=3 :

(0,0),(1,1),(4,3)

 i=4 :

  (0, 0), (1, 1), (4, 3), (5, 4)

 i = 5 

这个时候当前高度小于栈顶高度,我们认为栈顶已经不能向右扩展,所以弹出,并且获得面积 ( i  – H5.startindex) * H5.height = (5 – 4 ) * 5 = 5

弹出这个元素后,其实(4, 3)的高度也要比 1 大,所以把这个也弹出来,同样方式获得面积 8.

最后我们的堆栈是

(0,0),(1,1)

  i  = 6

   (0, 0), (1, 1), ( 3, 6)

  i = 7

  (0, 0), (1, 1), (3, 6)

 i = 8

最后一步是有点特殊的,因为我们必须要把所有的元素都弹出来,因为栈里面的高度,都坚持到了最后,我们要把这些高度组成的长方形拿出来检测。

我们可以假设扫面到8的时候,高度是0,(最小值)

弹出(3,6)获得面积 (8 – 6 ) * 3 = 6

弹出(1, 1)获得面积(8 – 1) * 1 = 7

最后的面积是8。

4、代码如下:

public class Test3 {
	public static void main(String[] args) {
		Integer[] array=new Integer[]{2,1,4,5,1,3,3};
		Integer max=countArea(array);
		System.out.println(max);
	}

        //histogram图形法:
	public static Integer countArea(Integer[] array){
		Stack<Node> stack = new Stack<Node>();
		stack.push(new Node(0,0));
		List<Integer> list=new ArrayList<Integer>();
		
		//扫面
		for(int i=0;i<=array.length;i++){

			//当将所有元素有扫了一遍之后,需要将栈堆弹空,并计算每一个矩形的面积
			if(i==array.length){
				//判断是否弹到第一个元素(0,0),是的话就结束,返回最大面积。
				while(stack.peek().getStartIndex()!=0){
					Integer area=(i+1-stack.peek().getStartIndex())*stack.peek().getHeight();
					list.add(area);
					stack.pop();
				}
				return Collections.max(list);
			}
			
			//新的元素比前一个元素的高度高,则入栈
			if(array[i]>=stack.peek().getHeight()){
				stack.push(new Node(array[i],i+1));
			}else{
				int index=0;
				
				//新的元素比前一个元素的高度高,则计算当前矩形的面积,并出栈
				while(array[i]<stack.peek().getHeight()){
					Integer area=(i+1-stack.peek().getStartIndex())*stack.peek().getHeight();
					list.add(area);
					index=stack.peek().getStartIndex();
					stack.pop();
				}
				//将新的元素入栈
				stack.push(new Node(array[i],index));
			}
		}
		return 0;
	}
}


//节点
class Node{
	//矩形高度
	Integer height;
	//矩形坐标
	Integer startIndex;
	
	Node(Integer height,Integer startIndex){
		this.height=height;
		this.startIndex=startIndex;
	}
	
	public Integer getHeight() {
		return height;
	}
	public void setHeight(Integer height) {
		this.height = height;
	}
	public Integer getStartIndex() {
		return startIndex;
	}
	public void setStartIndex(Integer startIndex) {
		this.startIndex = startIndex;
	}
}

上面代码可以换一种简介点的写法:

public class LargestRectangleArea {
	public int largestRectangleArea(int[] heights) {
		if(heights==null || heights.length==0) return 0;
		
		Stack<Integer> stack = new Stack<>();
		int res=0;
		
		for(int i=0;i<heights.length;i++){
			
			while(!stack.isEmpty() && heights[i]<=heights[stack.peek()]){
				int j=stack.pop();
				int k=stack.isEmpty()?-1:stack.peek();
				int curArea=(i-k-1)*heights[j];
				res=Math.max(res, curArea);
			}
			stack.push(i);
		}
		
		while(!stack.isEmpty()){
			int i=stack.pop();
			int k=stack.isEmpty()?-1:stack.peek();
			int curArea=(heights.length-k-1)*heights[i];
			res=Math.max(res, curArea);
		}
		
		return res;
    }
}

 

四、二维矩阵中的最大面积–Java代码实现:

介绍完histogram方法,我们也可以参照histogram方法解决二维矩阵中的最大面积问题。

1、步骤:

(1)接受控制台输入的参数;

(2)重新构造成直方图类型的矩阵。

例如:

重构前:
1 1 0 0 1
0 1 0 0 1
0 0 1 1 1
0 0 1 1 1
0 0 0 0 1
重构后:
1 2 0 0 5
0 1 0 0 4
0 0 2 2 3
0 0 1 1 2
0 0 0 0 1

其中,每一行的数字,代表以当前行为底,直方图的高度。

(3)遍历每一行的,算出当前二维数组的最大矩形面积:

2、完整代码:

package com.zwp.test1; 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;
/** 
* @version 创建时间:2018年8月24日 上午9:07:44 
* 类说明 :
* 给你一个二维矩阵,权值为False和True,找到一个最大的矩形,使得里面的值全部为True,输出它的面积
* 
给你一个矩阵如下
[
  [1, 1, 0, 0, 1],
  [0, 1, 0, 0, 1],
  [0, 0, 1, 1, 1],
  [0, 0, 1, 1, 1],
  [0, 0, 0, 0, 1]
]
输出6
*/
public class Test3 {

	public static void main(String[] args) {
		Integer[][] array = build();
		Integer[][] newArray=rebuild(array);
		
		List<Integer> area=new ArrayList<Integer>();
		for(int i=0;i<newArray.length;i++){
			Integer temp=countArea(newArray[i]);
			area.add(temp);
		}
		System.out.println(Collections.max(area));
	}
	
	//接收控制台输入的二维数组
	public static Integer[][] build(){
		Scanner in =new Scanner(System.in);
		int row=in.nextInt();
		int column=in.nextInt();
		
		Integer[][] array=new Integer[row][column];
		for(int i=0;i<row;i++){
			for(int j=0;j<column;j++){
				array[i][j]=in.nextInt();
			}
		}
		return array;
	}
	
	//重构二维数组,变成histogram类型。
	public static Integer[][] rebuild(Integer[][] array){
		
		Integer[][] newArray= new Integer[array.length][array[0].length];
		
		for(int i=0;i<array.length;i++){
			for(int j=0;j<array[0].length;j++){
				int height=0;
				for(int k=i;k<array.length;k++){
					if(array[k][j]==1){
						height+=1;
					}else{
						break;
					}
				}
				newArray[i][j]=height;
			}
		}
		return newArray;
	}
	
	//histogram图形法:
	public static Integer countArea(Integer[] array){
		Stack<Node> stack = new Stack<Node>();
		stack.push(new Node(0,0));
		List<Integer> list=new ArrayList<Integer>();
		
		//扫面
		for(int i=0;i<=array.length;i++){
			
			//当将所有元素有扫了一遍之后,需要将栈堆弹空,并计算每一个矩形的面积
			if(i==array.length){
				//判断是否弹到第一个元素(0,0),是的话就结束,返回最大面积。
				while(stack.peek().getStartIndex()!=0){
					Integer area=(i+1-stack.peek().getStartIndex())*stack.peek().getHeight();
					list.add(area);
					stack.pop();
				}
				return Collections.max(list);
			}
			
			//新的元素比前一个元素的高度高,则入栈
			if(array[i]>=stack.peek().getHeight()){
				stack.push(new Node(array[i],i+1));
			}else{
				int index=0;
				
				//新的元素比前一个元素的高度高,则计算当前矩形的面积,并出栈
				while(array[i]<stack.peek().getHeight()){
					Integer area=(i+1-stack.peek().getStartIndex())*stack.peek().getHeight();
					list.add(area);
					index=stack.peek().getStartIndex();
					stack.pop();
				}
				//将新的元素入栈
				stack.push(new Node(array[i],index));
			}
		}
		return 0;
	}
}


//节点
class Node{
	//矩形高度
	Integer height;
	//矩形坐标
	Integer startIndex;
	
	Node(Integer height,Integer startIndex){
		this.height=height;
		this.startIndex=startIndex;
	}
	
	public Integer getHeight() {
		return height;
	}
	public void setHeight(Integer height) {
		this.height = height;
	}
	public Integer getStartIndex() {
		return startIndex;
	}
	public void setStartIndex(Integer startIndex) {
		this.startIndex = startIndex;
	}
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114702.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号