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

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

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

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

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

核心思想

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

如圖，每一個(gè)輪次都是一次運(yùn)算，而我們的核心就是針對(duì)這每一個(gè)輪次的內(nèi)部的運(yùn)算。

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

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

代碼

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

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

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

測(cè)試

下面就對(duì)數(shù)組進(jìn)行測(cè)試。首先以本文開頭圖片上所示的數(shù)組來(lái)進(jìn)行測(cè)試吧。

Integer[] arr = {2,1,3,5,7,6,4}
···

數(shù)組中最大的連續(xù)的矩形區(qū)域的面積為： 16

然后我們修改一下數(shù)組中元素的值，來(lái)進(jìn)一步的測(cè)試看看結(jié)果是否正確。

Integer[] arr = {2,1,3,1,7,6,4}
···

數(shù)組中最大的連續(xù)的矩形區(qū)域的面積為： 12

經(jīng)博主本人親自測(cè)試，該算法可以正常的工作。 :)

優(yōu)化部分

說(shuō)道優(yōu)化部分，首先我們可以看出的估計(jì)便是最后的那步求結(jié)果集數(shù)組中的最大值了吧。

確實(shí)是的，我們其實(shí)可以另外申請(qǐng)一個(gè)變量，來(lái)記錄到目前為止的輪次的最大的那個(gè)子矩陣的面積的。不過(guò) 這點(diǎn)優(yōu)化而言起到的作用不是很大，時(shí)間復(fù)雜度也沒(méi)有什么比較大的改善。

另外一點(diǎn)，我覺(jué)的可以比較好的切入點(diǎn)就是對(duì)每一個(gè)輪次的進(jìn)行運(yùn)算的時(shí)候添加一個(gè)判斷，來(lái)決定當(dāng)前輪次之前是否往下循環(huán)。如果數(shù)組中的元素的波動(dòng)比較大的話，優(yōu)化的程度還是很不錯(cuò)的。

總結(jié)

這個(gè)小算法比較精巧，唯一比較缺憾的地方就是時(shí)間復(fù)雜度稍微的有點(diǎn)大了。如果讀者在尋求一種時(shí)間復(fù)雜度比較小的算法的話，請(qǐng)繞道咯。

如果只是想尋求一個(gè)結(jié)果，還是不錯(cuò)的。至少比暴力方式的計(jì)算效率高多了。

以上就是本文關(guān)于Java編程數(shù)組中最大子矩陣簡(jiǎn)便解法實(shí)現(xiàn)代碼的全部?jī)?nèi)容，希望對(duì)大家有所幫助。感興趣的朋友可以繼續(xù)參閱本站其他相關(guān)專題，如有不足之處，歡迎留言指出。感謝朋友們對(duì)本站的支持！