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

小咪咪 2024-03-23 13:29 34阅读 0赞

#### 文章目录 ####

*   *  前言
     *  题目
     *  分析
     *  算法
     *  实战
     *   *  1、创建算法方法
         *  2、创建测试用例
         *  3、查看测试结果
     *  写在最后

### 前言 ###

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

### 题目 ###

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。  
求在该柱状图中，能够勾勒出来的矩形的最大面积。  
![在这里插入图片描述][e98f1995c2134f3fb0bb924b9259f5b5.png]

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 \[2,1,5,6,2,3\]。  
![在这里插入图片描述][cffe5200cf74488db268039a7a192261.png]

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 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
         */
        @Test
        public 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社区’

[e98f1995c2134f3fb0bb924b9259f5b5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/faeea5c086144e83bb597e128cabe31e.png
[cffe5200cf74488db268039a7a192261.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/23/03085088c70d4394b503c14def3a7b67.png