最大矩形面积

[编程题]最大矩形面积

热度指数：7117 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一组非负整数组成的数组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

输出

算法知识视频讲解

JavaScript

w布响丸辣

借鉴前面的分治法：
var n = readline();
    var line = readline().split(' ');
    function largestarea(line){
        var len = line.length;
        var index = line.indexOf(Math.min.apply(null,line).toString());
        var value1 = line[index] * len;
        if(index!=0){
            var value2 = largestarea(line.slice(0, index));
        }else{
            var value2 = 0;
        }
        if(index!= len-1){
            var value3 = largestarea(line.slice(index+1));
        }else{
            var value3=0;
        }
        return Math.max(value1,value2,value3);
    }
    print(largestarea(line))

发表于 2018-10-08 18:42:15 回复(0)