算法—求最大矩形面积

题目

给定一组非负整数组成的数组h，代表一组柱状图的高度，其中每个柱子的宽度都为1。 在这组柱状图中找到能组成的最大矩形的面积（如图所示）。 入参h为一个整型数组，代表每个柱子的高度，返回面积的值。 输入描述: 输入包括两行,第一行包含一个整数n(1 ≤ n ≤ 10000) 第二行包括n个整数,表示h数组中的每个值,h_i(1 ≤ h_i ≤ 1,000,000)

输出描述: 输出一个整数,表示最大的矩阵面积。

示例1 输入： 6 2 1 5 6 2 3 输出：10

分析

对于每一块矩形，都找出它所在区域的面积area，并记录下来，最后取最大的那块面积maxarea返回。

1. 设置一个初始maxarea=0;
2. 对于每一块矩形（横坐标为i），找出它所在区域的左边界left：即往左数最左一个比它高的矩形的横坐标；
3. 找出它所在区域的右边界right：即往右数最右一个比它高的矩形的横坐标；
4. 记录当前区域的面积：area=height(i) * (right-left+1)
5. 若area>maxarea，则maxarea=area。

代码

/*
设一个当前最大面积：maxarea，初始化为0
对于每一块矩形，找到最左边比它高的矩形，作为当前区域的左边界left；
找到最右边比它高的矩形，作为当前区域的右边界right；
计算当前区域的面积：area=该矩形的高*(right-left+1)
若area>maxarea，则maxarea=area
*/
import java.util.Scanner;

public class Main{
    public static int getMaxarea(int height[]){
        int maxarea = 0; //当前最大面积
        int area = 0;//当前区域面积
        int left;//当前区域左边界
        int right;//当前区域右边界
        for(int i=0; i<height.length; i++){
            left = i; //初始化左边界
            right = i; //初始化右边界
            while(left>0 && height[left-1] >= height[i]){
                left--; //找到当前区域左边界
            }
            while(right<height.length-1 && height[right+1] >= height[i]){
                right++; //找到当前区域右边界
            }
            area = height[i] * (right-left+1);
            if(area > maxarea){
                maxarea = area;
            }
        }
        return maxarea;
    }
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int height[] = new int[a];
        for(int i=0; i<a; i++){
            height[i] = sc.nextInt();
        }
        int maxarea = getMaxarea(height);
        System.out.print(maxarea);
        sc.close();
    }
}

运行结果