求柱状图最大面积

浅浅的花香味﹌ 2022-06-07 00:43 244阅读 0赞

> 给定一组非负整数组成的数组h，代表一组柱状图的高度，其中每个柱子的宽度都为1。 在这组柱状图中找到能组成的最大矩形的面积（如图所示）。 入参h为一个整型数组，代表每个柱子的高度，返回面积的值。  
> ![这里写图片描述][58_1501040380059_47BE7E63FCFEB94676970280264AA19A]

代码实现：

public static int findLCS(int[] arr, int n) {
    
            int res = 0;
    
            int min = Integer.MAX_VALUE;
    
            for (int i = 0; i < n; i++) {
                min = Integer.MAX_VALUE;
                for (int j = i; j < n; j++) {
    
                    min = Math.min(min, arr[j]);
                    int cur = (j - i + 1) * min;
    
                    res = Math.max(cur, res);
               }
            }
    
            return res;
        }

变种的暴力破解法：

import java.util.Scanner;
    
    /*
     * 遍历数组每一个值，然后用两个指针从当前位置向两边寻找左右边界，大于等于当前值时则对应指针加1，
     * 这样最后得到以当前值为最小高度的矩形宽度，然后计算面积并与最大值比较并保存其中最大的值
     */
    public class Main {
        public static void main(String[] args){
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int[] height = new int[n];
            for(int i =0;i<n;i++){
                height[i] = sc.nextInt();
            }
    
            int maxArea = -1;
            for(int i = 0;i<n;i++){
                int left=i;
                int right=i;
    
              //计算以当前值为最小高度的矩形面积
                while(left > 0 && height[left-1] >= height[i])  left--;//寻找左边界
                while(right < n-1 && height[right+1] >= height[i])  right++;//寻找右边界
                int tempArea = (right-left+1) * height[i];
    
                if(maxArea<tempArea) maxArea=tempArea;
            }
    
            System.out.println(maxArea);
        }
    }

[58_1501040380059_47BE7E63FCFEB94676970280264AA19A]: /images/20220607/773bf019dbd34a1ca64a16ba33633b28.png