求柱状图最大面积-蒲公英云

求柱状图最大面积

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

代码实现：

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