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

相关推荐

  • leetcode215-数组中的第K个最大元素

    原题 在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 示例1: 输入: [3,2,1,5,6,4] 和…

    算法 2020年2月10日
    0140
  • leetcode887-鸡蛋掉落

    原题 你将获得 K 个鸡蛋,并可以使用一栋从 1 到 N 共有 N 层楼的建筑。 每个蛋的功能都是一样的,如果一个蛋碎了,你就不能再把它掉下去。 你知道存在楼层 F ,满足 0 &…

    算法 2020年4月11日
    0120
  • leetcode648-单词替换

    原题 在英语中,我们有一个叫做 词根(root)的概念,它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如,词根an,跟随着单词 oth…

    算法 2020年4月20日
    0150
  • leetcode79-单词搜索

    原题 给定一个二维网格和一个单词,找出该单词是否存在于网格中。 单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格…

    算法 2020年4月12日
    0130
  • leetcode119-杨辉三角II

    原题 给定一个非负索引 k,其中 k ≤ 33,返回杨辉三角的第 k 行。在杨辉三角中,每个数是它左上方和右上方的数的和。 示例: 输入: 3 输出: [1,3,3,1] 进阶: …

    2019年11月22日
    0280
  • leetcode380-常数时间插入、删除和获取随机元素

    原题 设计一个支持在平均 时间复杂度 O(1) 下,执行以下操作的数据结构。 insert(val):当元素 val 不存在时,向集合中插入该项。 remove(val):元素 v…

    2019年12月28日
    0110
  • leetcode234-回文链表

    原题 请判断一个链表是否为回文链表。 示例1: 输入: 1->2 输出: false 示例2: 输入: 1->2->2->1 输出: true 进阶: 你能否用 O(n) 时间复杂…

    2019年12月16日
    0120
  • leetcode73-矩阵置零

    原题 给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。 示例 1: 输入: [   [1,1,1],  …

    算法 2020年5月14日
    0130
  • leetcode283-移动零

    原题 给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 示例: 输入: [0,1,0,3,12] 输出: [1,3,12,0,0] 说…

    算法 2019年11月23日
    0110
  • leetcode145-二叉树的后序遍历

    原题 给定一个二叉树,返回它的 后序 遍历。 示例: 输入: [1,null,2,3]  1   \    2 &nbs…

    算法 2020年1月10日
    080

发表回复

登录后才能评论