您现在的位置是:首页 > 正文

剑指 Offer II 039. 直方图最大矩形面积

2024-02-01 02:37:48阅读 1

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

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

示例 1:

在这里插入图片描述

输入:heights = [2,1,5,6,2,3]
输出:10
解释:最大的矩形为图中红色区域,面积为 10
示例 2:

输入: heights = [2,4]
输出: 4

提示:

1 <= heights.length <=105
0 <= heights[i] <= 104

注意:本题与主站 84 题相同: https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/0ynMMM
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

本题如果使用分治的话,可能会超时,但是重要的是思想,下面的代码讲述了分治的解法:

首先,找到数组中最小的那个元素,此时的面积就是 end - start * 当前最小的 heights[minIndex]
然后,分别去这个最小元素的左边和右边去寻找,每次更新 最大值,找到的就是要的结果。

class Solution {
    public int largestRectangleArea(int[] heights) {
        return helper(heights, 0, heights.length);
    }
    public int helper(int[] heights, int start, int end) {
        if (start == end) {
            return 0;
        }
        if (start + 1 == end) {
            return heights[start];
        }
        int minIndex = start;
        for (int i = start + 1; i < end; i++) {
            if (heights[i] < heights[minIndex]) {
                minIndex = i;
            }
        }
        int area = (end - start) * heights[minIndex];
        int left = helper(heights, start, minIndex);
        int right = helper(heights, minIndex + 1, end);
        area = Math.max(area, left);
        return Math.max(area, right);
    }
}

本题真正想考的是单调栈,维护一定递增的数组,由于为了方便,我们在栈中存放的是数组的下标,当出现栈顶元素的高度大于当前元素的时候,需要将栈顶元素出栈,并计算当前最大的矩形面积,直到高度重新递增为止,在完成递增栈之后,再依次出栈直到栈中无元素

class Solution {
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxArea = -1;
        for (int i = 0; i < heights.length; i++) {
            while (stack.peek() != -1 && heights[stack.peek()] > heights[i]) {
                int height = heights[stack.pop()];
                int width = i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        while (stack.peek() != -1) {
                int height = heights[stack.pop()];
                int width = heights.length - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
        }
        return maxArea;
    }
}

网站文章

  • 如把联想电脑计算机图标放在桌面上,联想的电脑应用怎么放到桌面图标-?(图)...

    如把联想电脑计算机图标放在桌面上,联想的电脑应用怎么放到桌面图标-?(图)...

    如何将Lenovo的计算机应用程序放在桌面图标上? --- >>如何将我的计算机应用程序放置在桌面上,桌面图标似乎异常:1、该桌面图标消失,右键单击桌面上的鼠标,然后在桌面图标前面打勾。 2、桌面图标太大且不清楚,您可以调整屏幕分辨率。右键单击桌面,选择屏幕分辨率,并在调整为推荐值后按OK。 3如何将联想的计算机应用程序放置在桌面图标上如何将计算机管家软件管理放在桌面上? --- &g...

    2024-02-01 02:37:14
  • 2023 年 08 月编程语言排行榜,Julia 进入前 20

    2023 年 08 月编程语言排行榜,Julia 进入前 20

    架构师大咖 架构师大咖,打造有价值的架构师交流平台。分享架构师干货、教程、课程、资讯。架构师大咖,每日推送。公众号该公众号已被封禁TIOBE 2023 年 08 月份的编程语言排行榜已经公布,官方的标题是:Julia 第一次进入 TIOBE 指数前 20(Julia enters the TIOBE index t...

    2024-02-01 02:37:07
  • 【vulhub系列】cve-2018-1273S pring Expression Language 漏洞复现

    【vulhub系列】cve-2018-1273S pring Expression Language 漏洞复现

    记录一次cve-2018-1273S pring Expression Language漏洞复现

    2024-02-01 02:36:38
  • 游戏思考14:对cache_server缓冲服务器的问题思考(读云风博客有感)

    缓冲服务器的记录

    2024-02-01 02:36:30
  • zhang-Suen图像骨架提取(原理和代码)

    zhang-Suen图像骨架提取(原理和代码)

    转自东方fan的博客,感谢! 该算法有四个条件,若满足,则该点置为0。 或: 其中(a)(b)的意思为: 中心像素P1周围的目标像素(二值中的1)的个数之和在2和6之间。 8邻域像素中,按顺时针方向,...

    2024-02-01 02:36:22
  • 【leetcode-python】541. 反转字符串 II

    给定一个字符串 s 和一个整数 k,你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。 如果剩余字符少于 k 个,则将剩余字符全部反转。 如果剩余字符小于 2k 但大于或等于 k ...

    2024-02-01 02:36:15
  • 3-Flutter常用组件--标题栏和状态栏

    3-Flutter常用组件--标题栏和状态栏

    文章目录1.BottomAppBar属性2.BottomNavigationBar属性BottomNavigationBarItem3.SliverAppBar属性1.FlexibleSpaceBar...

    2024-02-01 02:35:45
  • JS 常用数组

    JS 常用数组

    从 0 开始计算的索引,表示要开始改变数组的位置一个整数,表示数组中要从start开始删除的元素数量。(0代表不删除)item1itemN从start开始要加入到数组中的元素(如果不指定,那不增加元素)

    2024-02-01 02:35:38
  • 利用图神经网络进行药物再利用的计算方法(下)

    利用图神经网络进行药物再利用的计算方法(下)

    本研究提出了一种图神经网络药物再利用模型,我们称之为GDRnet,以有效地筛选大型批准药物数据库,并预测新疾病的可能治疗方法。我们将药物再利用作为一个多层异构网络中的链接预测问题,该网络约有140万条...

    2024-02-01 02:35:33
  • Java反射调用ashx

    Java反射调用ashx

    Java发送调用jar包的方法,转换为基类接口调用

    2024-02-01 02:35:05