Java編程數組中最大子矩陣簡便解法實現代碼

2024-07-13 10:17:23

字體：大中小

來源：轉載

供稿：網友

本文研究的主要是Java編程數組中最大子矩陣的相關內容，具體介紹如下。

java,數組,最大子矩陣,java數組矩陣,矩陣轉數組

遇到一個好人，可以改變一生；遇到一本好書，又何嘗不是呢？

最近在翻閱左程云先生的《程序員代碼面試指南–IT名企算法與數據結構題目最優解》時就非常的有感悟。建議有這方面愛好的博友，也去觀摩觀摩。

書中講解的基于棧的數組的最大矩陣的算法很經典，但是博主能力有限，沒能徹底的領悟該算法的精髓，但是根據這個思想，博主想出了一種簡易的應對該類問題的算法，現概述如下。

核心思想

先來看一張圖吧，我們就可以大致的理解了。

java,數組,最大子矩陣,java數組矩陣,矩陣轉數組

如圖，每一個輪次都是一次運算，而我們的核心就是針對這每一個輪次的內部的運算。

計算出每一層連續不間斷的最大長度

也就是說，我們是最這個數組進行由下至上的輪次計算，然后針對每一輪就可以計算出本輪次可以得出的連續最大子矩陣的面積。然后只需要比較每一個輪次的最大的那個數據，返回就可以求出該數組最大的連續的子矩陣的面積了。

代碼

好了，有了上面的核心思想的鋪墊，我們就可以著手編寫代碼了。（雖然我也覺得自己并沒有說的很清楚，見諒見諒）。

java;">package stack_and_queue;/** * @author 郭 璞<br> *  根據數組來計算連續的最大的矩形區域的面積 */public class MaxRectangle {	public static void main(String[] args) {		Integer[] arr = { 2, 1, 3, 5, 7, 6, 4 };		Integer maxRectangle = maxRectangleArea(arr);		System.out.println("數組中最大的連續的矩形區域的面積為： " + maxRectangle);	}	/** * @param arr * @return 數組中連續矩形區域的最大面積 */	private static Integer maxRectangleArea(Integer[] arr) {		int[] result = new int[arr.length];		// 對數組進行遍歷式的計算，由底向上不間斷的連續長度		for (int i = 1; i <= arr.length; i++) {			// 當前輪次 中實現對連續長度的累加的臨時取值			int templen = 0;			// 記錄本輪高度下的最大連續長度			int templen_max = 0;			// 內層循環應該是從數組首部開始，而從當先層下標開始會導致前面部分數據的丟失			for (int j = 1; j <= arr.length; j++) {				if (arr[j - 1] >= i) {					templen += 1;					templen_max = templen;				} else {					templen = 0;				}			}			result[i - 1] = i * templen_max;			// System.out.println("第" + i + "層連續不間斷的最大長度為：" + templen_max);		}		// 求得結果集數組中數值最大的那個數，即為所求連續區域中的最大的矩形域的面積		int maxArea = 0;		for (int i = 0; i < result.length; i++) {			maxArea = maxArea > result[i] ? maxArea : result[i];		}		// 將所求得的最大連續矩形域的面積返回		return maxArea;	}}

代碼中的注釋也比較的全面，就不再過多的贅述了。

測試

下面就對數組進行測試。首先以本文開頭圖片上所示的數組來進行測試吧。