Java編程數(shù)組中最大子矩陣簡便解法實現(xiàn)代碼

更新時間：2018年01月26日 16:33:53 作者：Marksinoberg

這篇文章主要介紹了Java編程數(shù)組中最大子矩陣簡便解法實現(xiàn)代碼，小編覺得還是挺不錯的，具有一定借鑒價值，需要的朋友可以參考下

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

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

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

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

核心思想

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

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

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

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

代碼

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

package stack_and_queue;
/**
 * @author 郭 璞<br>
 *  根據(jù)數(shù)組來計算連續(xù)的最大的矩形區(qū)域的面積
 */
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("數(shù)組中最大的連續(xù)的矩形區(qū)域的面積為： " + maxRectangle);
	}
	/**
 * @param arr
 * @return 數(shù)組中連續(xù)矩形區(qū)域的最大面積
 */
	private static Integer maxRectangleArea(Integer[] arr) {
		int[] result = new int[arr.length];
		// 對數(shù)組進行遍歷式的計算，由底向上不間斷的連續(xù)長度
		for (int i = 1; i <= arr.length; i++) {
			// 當前輪次 中實現(xiàn)對連續(xù)長度的累加的臨時取值
			int templen = 0;
			// 記錄本輪高度下的最大連續(xù)長度
			int templen_max = 0;
			// 內層循環(huán)應該是從數(shù)組首部開始，而從當先層下標開始會導致前面部分數(shù)據(jù)的丟失
			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 + "層連續(xù)不間斷的最大長度為：" + templen_max);
		}
		// 求得結果集數(shù)組中數(shù)值最大的那個數(shù)，即為所求連續(xù)區(qū)域中的最大的矩形域的面積
		int maxArea = 0;
		for (int i = 0; i < result.length; i++) {
			maxArea = maxArea > result[i] ? maxArea : result[i];
		}
		// 將所求得的最大連續(xù)矩形域的面積返回
		return maxArea;
	}
}

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

測試

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