84. 柱状图中最大的矩形


2019-02-12 13:54:03 by Sikoay with 0 comments 1 Hits
Blog 1

用的暴力搜索,计算每个height最大的面积大小,然后保留最大的面积,其中用了一些简单的跳过方法,正在研究大神是怎么写的

问题:

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

 

以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]

 

图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10 个单位。

 

示例:

输入: [2,1,5,6,2,3]
输出: 10

解答:

 

class Solution {
    function largestRectangleArea($heights) {
        $max_area = 0;
        for($i = 0;$i < count($heights);$i++){
            $height = $heights[$i];
            $width = 1;
            
            if($height == 0){
                continue;
            }
            for($n = $i-1;$n >= 0;$n--){
                if($heights[$n] > $height){
                    $width++;
                }else if ($heights[$n] == $height){
                    continue 2;
                }else{
                    break 1;
                }
            }
            for($m = $i+1;$m < count($heights);$m++){
                if($heights[$m] >= $height){
                    $width++;
                }else{
                    break;
                }
            }
            if($max_area < $width * $height){
                $max_area = $width * $height;
            }
        }
        return $max_area;
    }
}

 

 

Tags:

回复 (0)

Leave a Comment