Java编程数组中最大子矩阵简便解法实现代码

来源：本站原创|时间：2020-01-10|栏目：Java编程|点击：次

本文研究的主要是Java编程数组中最大子矩阵的相关内容，具体介绍如下。

遇到一个好人，可以改变一生；遇到一本好书，又何尝不是呢？

最近在翻阅左程云先生的《程序员代码面试指南–IT名企算法与数据结构题目最优解》时就非常的有感悟。建议有这方面爱好的博友，也去观摩观摩。

书中讲解的基于栈的数组的最大矩阵的算法很经典，但是博主能力有限，没能彻底的领悟该算法的精髓，但是根据这个思想，博主想出了一种简易的应对该类问题的算法，现概述如下。

核心思想

先来看一张图吧，我们就可以大致的理解了。

如图，每一个轮次都是一次运算，而我们的核心就是针对这每一个轮次的内部的运算。

计算出每一层连续不间断的最大长度

也就是说，我们是最这个数组进行由下至上的轮次计算，然后针对每一轮就可以计算出本轮次可以得出的连续最大子矩阵的面积。然后只需要比较每一个轮次的最大的那个数据，返回就可以求出该数组最大的连续的子矩阵的面积了。

代码

好了，有了上面的核心思想的铺垫，我们就可以着手编写代码了。（虽然我也觉得自己并没有说的很清楚，见谅见谅）。

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

代码中的注释也比较的全面，就不再过多的赘述了。

测试

下面就对数组进行测试。首先以本文开头图片上所示的数组来进行测试吧。