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

相关推荐

  • leetcode636-函数的独占时间

    原题 给出一个非抢占单线程CPU的 n 个函数运行日志,找到函数的独占时间。 每个函数都有一个唯一的 Id,从 0 到 n-1,函数可能会递归调用或者被其他函数调用。 日志是具有以…

    算法 2020年2月2日
    0190
  • leetcode160-相交链表

    原题 编写一个程序,找到两个单链表相交的起始节点。 如下面的两个链表: 在节点 c1 开始相交。 示例 1: 输入: intersectVal = 8, listA = [4,1,…

    2019年12月14日
    090
  • leetcode561-数组拆分I

    原题 给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ,使得从1 到 n 的 min(ai, b…

    算法 2019年11月18日
    080
  • leetcode138-复制带随机指针的链表

    这道题和leetcode133-克隆图有异曲同工之妙。 原题 给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深拷贝。…

    2019年12月17日
    0330
  • leetcode215-数组中的第K个最大元素

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

    算法 2020年2月10日
    0140
  • 剑指offer17-打印从1到最大的n位数

    原题(来源Leetcode) 输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。 示例 1: 输入: …

    算法 2020年4月17日
    080
  • leetcode752-打开转盘锁

    原题 你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'。每个拨轮可以自由…

    2019年12月9日
    0280
  • leetcode3-无重复字符的最长子串

    原题 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc",所以其长…

    2019年12月26日
    0100
  • leetcode173-二叉搜索树迭代器

    原题 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。 示例: BSTIterator iterator…

    2020年1月16日
    050
  • 剑指offer46-把数字翻译成字符串

    原题 给定一个数字,我们按照如下规则把它翻译为字符串:0 翻译成 “a” ,1 翻译成 “b”,……,11 翻译成 “l”,……,25 翻译成 “z”。一个数字可能有多个翻译。请编…

    算法 2020年2月29日
    0290

发表回复

登录后才能评论