【每日一练】JAVA算法求柱状图中最大的矩形面积

前言

作为一名以JAVA语言为主的搬砖人，学习掌握好函数语法很重要，但是算法也是需要掌握的。今天我们就分享一个求柱状图中最大的矩形面积的题目，这个题目较为简单。

题目

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:
输入: [2,1,5,6,2,3]
输出: 10

分析

1、根据题意我们可以知道数组元素就是各个柱状图的高度，宽度默认都是1；
2、形成矩形肯定是一个或多个相邻的柱子组合而成，这个组合的矩形面积是最短的柱子高度乘以总的宽度

算法

1、从第一个柱子作为起点，依次与后续柱子组合；
2、默认起始长方形宽度为1，每组合一个柱子宽度+1，后续柱子高度减少则组成的长方形高度减少；
3、根据每个组合计算该组形成的长方形面积，与最大面积比较（初始面积默认0）；
4、根据第3步骤比较结果，如果大于最大面积则替换最大面积元素组合以及最大面积；
5、循环2、3、4步骤，最后的组合则是可以组成最大面积的组合，最后的面积就是最大面积。

实战

我们用JAVA语言演示

1、创建算法方法

/* 最大面积计算* 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。* 求在该柱状图中，能够勾勒出来的矩形的最大面积。* @author senfel* @version 1.0* @date 2023/4/17 14:08*/
public class AreaDemo {/* 获取最大面积* @param array 柱子高度数组，宽度默认1* @author senfel* @date 2023/4/17 14:09* @return int*/public static int getMaxArea(int[] array){//初始化面积int maxArea = 0;if(array == null || array.length == 0){return maxArea;}//初始化数组StringBuffer maxEleStr = new StringBuffer();for(int i=0;i<array.length;i++){//组成当前长方形的元素StringBuffer currentEleStr = new StringBuffer();//宽度int width = 1;//高度int nowHeight = array[i];//组合的初始元素currentEleStr.append(array[i]);if(maxArea < width * nowHeight){maxArea = width * nowHeight;maxEleStr =currentEleStr;}//依次与后续柱子组合for(int j = i+1;j<array.length;j++){//长方形宽度增加width++;if(array[j] < nowHeight){//长方形高度减少nowHeight = array[j];}if(maxArea < width * nowHeight){//组成长方形的元素if(j>i){currentEleStr.append(",");}currentEleStr.append(array[j]);maxArea =  width * nowHeight;maxEleStr = currentEleStr;}}}System.err.println("组成最大长方形的元素为：["+maxEleStr.toString()+"]");return maxArea;}}

2、创建测试用例

@SpringBootTest
class DemoApplicationTests {/* 计算组成最大面积长方形* @author senfel* @date 2023/4/17 15:06* @return void*/@Testpublic void areaTest(){int[] array = {2,1,5,6,2,3};int maxArea = AreaDemo.getMaxArea(array);System.err.println("组成最大长方形的最大面积为："+maxArea);}
}

3、查看测试结果

见证奇迹的时刻

组成最大长方形的元素为：[5,6]
组成最大长方形的最大面积为：10

写在最后

JAVA计算柱状图中最大的矩形面积算法较为简单，只要从第一个到最后一个元素依次与后续元素进行组合判断即可。其中重难点是后续元素大小决定了长方形的高度，以及每增加一个元素长方形的宽度也要增加，只要把握住这两个点写出算法轻而易举。

路漫漫其修远兮，吾将上下而求索
有兴趣的小伙伴也可以加我：
订阅号 ‘架构集结号’
知识星球 ‘Coding社区’

杭州女装