一、原題：

給你一個二維矩陣，權值為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來做。

看到這里，可能有些人會不明白什么是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， 對應的柱形圖如下，最后求出來的面積最大的圖如右圖所示。

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;} }

?

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的二维矩阵中的最大矩形面积--java实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。