leetcode84-柱状图中最大的矩形

原题

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

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

leetcode84-柱状图中最大的矩形

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

leetcode84-柱状图中最大的矩形

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

示例:

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

解法

思想

这道题和leetcode42-接雨水较为相似。

对于每列来说,以当前列高为高的最大矩形区域的宽度区域为被左边最近较矮一列和右边最近较矮一列围起来的宽度。

如果两边有一边没有比当前列矮的一列,则左边算作-1,右边算作length。

代码

class Solution {
    public int largestRectangleArea(int[] heights) {
        int length = heights.length;
        if(length==0) return 0;
        int max = 0;
        int left[] = new int[length];
        int right[] = new int[length];
        left[0] = -1;
        right[length-1] = length;
        for(int i = 1;i<length;i++){
            //如果左边一列比当前列矮,则left就等于左边一列的下标。
            if(heights[i]>heights[i-1]) left[i] = i-1;
            else{
                //否则沿着左边这列的left一直查找过去,直到找到比当前列低的一列
                left[i] =  left[i-1];
                while(left[i]!=-1&&heights[left[i]]>=heights[i])
                    left[i] = left[left[i]];
            }
        }
        for(int i = length-2;i>=0;i--){
            //如果右边一列比当前列矮,则right就等于右边一列的下标。
            if(heights[i]>heights[i+1]) right[i] = i+1;
            else{
                //否则沿着右边这列的right一直查找过去,直到找到比当前列低的一列
                right[i] =  right[i+1];
                while(right[i]!=length&&heights[right[i]]>=heights[i])
                    right[i] = right[right[i]];
            }
        }
        for(int i = 0;i<length;i++){
            int area = (right[i]-left[i]-1)*heights[i];
            if(area>max) max = area;
        }
        return max;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode84-%e6%9f%b1%e7%8a%b6%e5%9b%be%e4%b8%ad%e6%9c%80%e5%a4%a7%e7%9a%84%e7%9f%a9%e5%bd%a2/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年1月23日 21:14
下一篇 2020年1月24日 13:19

相关推荐

  • leetcode5-最长回文子串

    原题 给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例1: 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有…

    算法 2020年2月20日
    0110
  • leetcode278-第一个错误的版本

    原题 你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。 假…

    算法 2020年1月2日
    080
  • leetcode700-二叉搜索树中的搜索

    原题 给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。 例如, 给定二叉搜索树…

    算法 2020年1月16日
    090
  • leetcode841-钥匙和房间

    原题 有 N 个房间,开始时你位于 0 号房间。每个房间有不同的号码:0,1,2,...,N-1,并且房间里可能有一些钥匙能使你进入下一个房间。 在形式上,对于每个房间 i 都有一…

    2019年12月13日
    0110
  • leetcode47-全排列II

    原题 给定一个可包含重复数字的序列,返回所有不重复的全排列。 示例: 输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ] 解法 思想 这道题…

    算法 2020年5月10日
    090
  • 一致性哈希算法的介绍

    本文参考资源: 一致性Hash算法详解 - 知乎 一致性哈希算法概述 分布式系统中,常常听到一种算法叫一致性哈希算法,而最常用的领域相信大家也有所耳闻——负载均衡。负载均衡有许多算…

    2020年4月4日
    070
  • leetcode56-合并区间

    原题 给出一个区间的集合,请合并所有重叠的区间。 示例 1: 输入: [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]]…

    算法 2020年4月16日
    0160
  • leetcode365-水壶问题

    原题 有两个容量分别为 x升 和 y升 的水壶以及无限多的水。请判断能否通过使用这两个水壶,从而可以得到恰好 z升 的水? 如果可以,最后请用以上水壶中的一或两个来盛放取得的 z升…

    算法 2020年3月21日
    0190
  • leetcode403-青蛙过河

    原题 一只青蛙想要过河。 假定河流被等分为 x 个单元格,并且在每一个单元格内都有可能放有一石子(也有可能没有)。 青蛙可以跳上石头,但是不可以跳入水中。 给定石子的位置列表(用单…

    算法 2020年6月16日
    04510
  • leetcode945-使数组唯一的最小增量

    原题 给定整数数组 A,每次 move 操作将会选择任意 A[i],并将其递增 1。 返回使 A 中的每个值都是唯一的最少操作次数。 示例 1: 输入: [1,2,2] 输出: 1…

    算法 2020年3月22日
    0630

发表回复

登录后才能评论