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

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

测试

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

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

数组中最大的连续的矩形区域的面积为： 16

然后我们修改一下数组中元素的值，来进一步的测试看看结果是否正确。

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

数组中最大的连续的矩形区域的面积为： 12

经博主本人亲自测试，该算法可以正常的工作。 :)

优化部分

说道优化部分，首先我们可以看出的估计便是最后的那步求结果集数组中的最大值了吧。

确实是的，我们其实可以另外申请一个变量，来记录到目前为止的轮次的最大的那个子矩阵的面积的。不过 这点优化而言起到的作用不是很大，时间复杂度也没有什么比较大的改善。

另外一点，我觉的可以比较好的切入点就是对每一个轮次的进行运算的时候添加一个判断，来决定当前轮次之前是否往下循环。如果数组中的元素的波动比较大的话，优化的程度还是很不错的。

总结

这个小算法比较精巧，唯一比较缺憾的地方就是时间复杂度稍微的有点大了。如果读者在寻求一种时间复杂度比较小的算法的话，请绕道咯。

如果只是想寻求一个结果，还是不错的。至少比暴力方式的计算效率高多了。

以上就是本文关于Java编程数组中最大子矩阵简便解法实现代码的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

您可能感兴趣的文章:

  • 堆排序实例(Java数组实现)
  • Java数组扩容实例代码
  • java编程中拷贝数组的方式及相关问题分析
  • java数组复制的四种方法效率对比
  • Java中的数组复制（clone与arraycopy）代码详解
  • 浅谈java中字符串数组、字符串、整形之间的转换
  • java数组基础详解
  • Java数组越界问题实例解析
赞 (0)

相关推荐

  • 堆排序实例(Java数组实现)

    堆排序:利用大根堆 数组全部入堆,再出堆从后向前插入回数组中,数组就从小到大有序了. public class MaxHeap<T extends Comparable<? super T>> { private T[] data; private int size; private int capacity; public MaxHeap(int capacity) { this.data = (T[]) new Comparable[capacity + 1]; size =

  • java数组复制的四种方法效率对比

    java数组复制的四种方法效率对比

    有关数组的基础知识,有很多方面,比方说初始化,引用,遍历,以及一维数组和二维数组,今天我们先看看数组复制的有关内容. 来源于牛客网的一道选择题: JAVA语言的下面几种数组复制方法中,哪个效率最高? A.for循环逐一复制 B.System.arraycopy C.System.copyof D.使用clone方法 效率:System.arraycopy>clone>Arrays.copyOf>for循环 1.System.arraycopy的用法: public static void

  • Java数组越界问题实例解析

    Java中数组初始化和OC其实是一样的,分为动态初始化和静态初始化, 动态初始化:指定长度,由系统给出初始化值 静态初始化:给出初始化值,由系统给出长度 在我们使用数组时最容易出现的就是数组越界问题,好了,这里有个简单的例子 int [][] array = {{1,2,3},{1,4}}; System.out.println(array[1][2]); 这是一个二维数组,很明显,数组越界了,控制台中会打印如下信息: Exception in thread "main" java.l

  • 浅谈java中字符串数组、字符串、整形之间的转换

    字符串数组转字符串(只能通过for循环): String[] str = {"abc", "bcd", "def"}; StringBuffer sB = new StringBuffer(); for (int i = 0; i < str.length;i++) { sB.append(str[i]); } String s = sB.toString(); 字符数组转字符串可以通过下面的方式: char[] data = {"

  • java编程中拷贝数组的方式及相关问题分析

    JAVA数组的复制是引用传递,而并不是其他语言的值传递. 这里介绍java数组复制的4种方式极其问题: 第一种方式利用for循环: int[] a={1,2,4,6}; int length=a.length; int[] b=new int[length]; for (int i = 0; i < length; i++) { b[i]=a[i]; } 第二种方式直接赋值: int[] array1={1,2,4,6}; int[] array2=a; 这里把array1数组的值复制给arra

  • java数组基础详解

    数组 数组(Array):相同类型数据的集合. Java 数组初始化的两种方法: 静态初始化: 程序员在初始化数组时为数组每个元素赋值: 动态初始化: 数组初始化时,程序员只指定数组的长度,由系统为每个元素赋初值. 数组是否必须初始化 对于这个问题,关键在于要弄清楚数组变量和数组对象的差别.数组变量是存放在栈内存中的,数组对象是存放在堆内存中的.数组变量只是一个引用变量,他能够指向实际的数组对象. 所谓的数组初始化并非对数组变量初始化,而是对数组对象进行初始化. 定义数组 方式1(推荐,更能表明

  • Java数组扩容实例代码

    在写程序的过程中,我们常常会碰见数组空间不够用的情况,比如我已经初始化了一个数组int []a = {1,2,3,4,5,6,7,8,9,10} ;这时,我想往数组下标3的位置插入一个元素,该怎么做?用C语言实现太难了吧,需要调用memcpy函数要一个一个偏,但是在java中就不用那么麻烦了,有种叫数组的扩容方式,轻松实现.来看看代码: public class HelloWorld { public static void main(String[] args){ // Scanner s =

  • Java中的数组复制（clone与arraycopy）代码详解

    JAVA数组的复制是引用传递,而并不是其他语言的值传递. 1.clone protectedObjectclone() throwsCloneNotSupportedException创建并返回此对象的一个副本."副本"的准确含义可能依赖于对象的类.这样做的目的是,对于任何对象x,表达式: x.clone()!=x为true,表达式: x.clone().getClass()==x.getClass()也为true,但这些并非必须要满足的要求.一般情况下: x.clone().equa

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

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

    本文研究的主要是Java编程数组中最大子矩阵的相关内容,具体介绍如下. 遇到一个好人,可以改变一生:遇到一本好书,又何尝不是呢? 最近在翻阅 左程云先生的<程序员代码面试指南–IT名企算法与数据结构题目最优解>时就非常的有感悟.建议有这方面爱好的博友,也去观摩观摩. 书中讲解的基于栈的数组的最大矩阵的算法很经典,但是博主能力有限,没能彻底的领悟该算法的精髓,但是根据这个思想,博主想出了一种简易的应对该类问题的算法,现概述如下. 核心思想 先来看一张图吧,我们就可以大致的理解了. 如图,每一个轮

  • Java编程实现中英混合字符串数组按首字母排序的方法

    本文实例讲述了Java编程实现中英混合字符串数组按首字母排序的方法.分享给大家供大家参考,具体如下: 在Java中对于字符串数组的排序,我们可以使用Arrays.sort(String[])方法很便捷的进行排序.例如: String[] arrays = new String[] { "gyu", "sdf", "zf", "大同", "收到", "地方", "三等分"

  • java删除数组中的某一个元素的方法

    实例如下: package org.company.project.test; import java.util.Arrays; import java.util.Scanner; public class ArraysDelete { public static void main(String[] args) { //删除数组中的某一个元素的方法: //把最后一个元素替代指定的元素,然后数组缩容 Scanner sc =new Scanner(System.in); int[] arr =

  • Java编程GUI中的事件绑定代码示例

    程序绑定的概念: 绑定指的是一个方法的调用与方法所在的类(方法主体)关联起来.对java来说,绑定分为静态绑定和动态绑定:或者叫做前期绑定和后期绑定 静态绑定: 在程序执行前方法已经被绑定,此时由编译器或其它连接程序实现.例如:C. 针对java简单的可以理解为程序编译期的绑定:这里特别说明一点,java当中的方法只有final,static,private和构造方法是前期绑定 动态绑定 后期绑定:在运行时根据具体对象的类型进行绑定. 若一种语言实现了后期绑定,同时必须提供一些机制,可在运行期间

  • java编程无向图结构的存储及DFS操作代码详解

    java编程无向图结构的存储及DFS操作代码详解

    图的概念 图是算法中是树的拓展,树是从上向下的数据结构,结点都有一个父结点(根结点除外),从上向下排列.而图没有了父子结点的概念,图中的结点都是平等关系,结果更加复杂. 无向图                                                       有向图 图G=(V,E),其中V代表顶点Vertex,E代表边edge,一条边就是一个定点对(u,v),其中(u,v)∈V. 这两天遇到一个关于图的算法,在网上找了很久没有找到java版的关于数据结构中图的存储及其

  • Java编程实现轨迹压缩之Douglas-Peucker算法详细代码

    Java编程实现轨迹压缩之Douglas-Peucker算法详细代码

    第一部分 问题描述 1.1 具体任务 本次作业任务是轨迹压缩,给定一个GPS数据记录文件,每条记录包含经度和维度两个坐标字段,所有记录的经纬度坐标构成一条轨迹,要求采用合适的压缩算法,使得压缩后轨迹的距离误差小于30m. 1.2 程序输入 本程序输入是一个GPS数据记录文件. 1.3 数据输出 输出形式是文件,包括三部分,压缩后点的ID序列及坐标.点的个数.平均距离误差.压缩率 第二部分 问题解答 根据问题描述,我们对问题进行求解,问题求解分为以下几步: 2.1 数据预处理 本次程序输入为GPS

  • java编程实现并查集的路径压缩代码详解

    java编程实现并查集的路径压缩代码详解

    首先看两张路径压缩的图片: 并查集(Union-find Sets)是一种非常精巧而实用的数据结构,它主要用于处理一些不相交集合的合并问题.一些常见的用途有求连通子图.求最小生成树的 Kruskal 算法和求最近公共祖先(Least Common Ancestors, LCA)等. 使用并查集时,首先会存在一组不相交的动态集合 S={S 1 ,S 2 ,⋯,S k } ,一般都会使用一个整数表示集合中的一个元素. 每个集合可能包含一个或多个元素,并选出集合中的某个元素作为代表.每个集合中具体包含

  • java编程两种树形菜单结构的转换代码

    首先看看两种树形菜单结构的代码示例. SingleTreeNode: package com.zzj.tree; public class SingleTreeNode { private int id; private int pId; private String name; public SingleTreeNode() { } public SingleTreeNode(int id, int pId, String name) { this.id = id; this.pId = pI

  • Java编程实现对十六进制字符串异或运算代码示例

    Java编程实现对十六进制字符串异或运算代码示例

    前言:好久没有写博客,最近一年感觉真是好忙,各种做不完的工作.相信很多上班族都会有这种感觉.最近对NFC进行写卡操作,需要计算一个校验位.一般情况下,校验位多数是由前几个字节进行异或运算所得. 现在我就先说一下我使用的场景: 把一个16字节的数据写到CPU卡(如交通卡)里面,最后一字节是校验码---前十五字节异或. 我开始从网上找了一些别人写的算法发现计算后结果不对,或者就是写的太复杂了,于是自己就写了一个,感觉也比较简单,现在分享给大家,希望一起交流一下. 第一节:什么是异或运算(主要摘自百度

  • Java编程二项分布的递归和非递归实现代码实例

    Java编程二项分布的递归和非递归实现代码实例

    本文研究的主要内容是Java编程二项分布的递归和非递归实现,具体如下. 问题来源: 算法第四版 第1.1节 习题27:return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p); 计算递归调用次数,这里的递归式是怎么来的? 二项分布: 定义:n个独立的是/非试验中成功次数k的离散概率分布,每次实验成功的概率为p,记作B(n,p,k). 概率公式:P(ξ=K)= C(n,k) * p^k * (1-p)^(n-k

随机推荐