文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

☆打卡算法☆LeetCode 85、最大矩形 算法解析

一、题目 1、算法题目 “给定包含0和1的二维矩阵，找出只包含1的最大矩阵，返回其面积。” 题目链接： 来源：力扣（LeetCode） 链接：85....最大矩形 - 力扣（LeetCode） (leetcode-cn.com) 2、题目描述 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积...首先，说一下暴力解法：列举所有可能出现的矩形，枚举矩形所有的左上角和右下角坐标，并检查该矩形是否是面积最大的，但是这样做时间复杂度过高，会超时。我发现在学算法之前我写出来的算法都是暴利解法。。。...那么就可以使用单调栈的做法，找到最高的柱子，并找到它左右的最大高度，拼接成最大的矩形，得到面积就是想要的结果。...思路就是： 枚举矩形的下边界，枚举下边界的每一列的高度 找到最高的柱子向左右寻找最大的矩形 得到矩形求出面积

58220
    • 您找到你想要的搜索结果了吗？
    是的
    没有找到

    矩形最大面积

    1 引言 矩形的面积等于长乘以宽，矩形的周长是四条边的和，给定周长让我们算面积的最大值，人为笔算会很麻烦，但用python求解矩形的的面积的最大值，可以使我们运算起来更便捷。...2 问题 给定一个长度为n (n能被4整除) 的绳子，求能围成的最大矩形面积是多少？所围成的矩形任意一条边长度不低于1。...示列 输入: 4 输出: 1 3 方法 先给出矩形的周长n，再设矩形的长宽分别为x，y（x，y的范围为[1,n)）。再用if条件判断2*（x+y）= n。...再将其每次的面积s存入列表中，用max函数求出最大值。 4 实验结果与讨论 通过实验、实践等证明提出的方法是有效的，是能够解决开头提出的问题。...，要注意在用if条件判断时，是长和宽的和的二倍等于周长，用python求矩形面积要熟练掌握for in 双循环。

    67810

    ☆打卡算法☆LeetCode 84、柱状图中最大的矩形 算法解析

    一、题目 1、算法题目 “给定n个非负整数，用来表示柱状图每个柱子的高度，求柱状图中最大的矩形的面积。” 题目链接： 来源：力扣（LeetCode） 链接：84....柱状图中最大的矩形 - 力扣（LeetCode） (leetcode-cn.com) 2、题目描述 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。...求在该柱状图中，能够勾勒出来的矩形的最大面积。...首先，来思考一下如何去求最大矩形，找到某一根柱子，将其固定为矩形的高度h，随后根据这根柱子向左右延伸，直到遇到高度小于h的柱子，这样就确定了矩形的左右边界，边界的宽度为w，面积为h * w。...OK，首先说一下什么是单调栈，单调栈是一种很经典的数据结构，里面存放的数据都是有序的，可以分为单调递增站和单调递减栈，常用于解决最大区间、最大视野、最大矩形等。

    26340

    最大矩形

    题目描述 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。...柱状图中最大的矩形】多种方法（Python3）[1] 使用了多种方法来解决。然而在这道题，我们仍然可以使用完全一样的思路去完成。不熟悉的可以看下我的题解。本题解是基于那道题的题解来进行的。...,"0"], ["1","0","1","1","1"], ["1","1","1","1","1"], ["1","0","0","1","0"] ] 我们逐行扫描得到 84.柱状图中最大的矩形...这样我们就可以使用84.柱状图中最大的矩形 中的解法来进行了，这里我们使用单调栈来解。...柱状图中最大的矩形】多种方法（Python3）: https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-

    62920

    最大矩形 —— 单调栈「建议收藏」

    题意： 给定从左到右多个矩形，已知这此矩形的宽度都为1，长度不完全相等。这些矩形相连排成一排，求在这些矩形包括的范围内能得到的面积最大的矩形，打印出该面积。...所求矩形可以横跨多个矩形，但不能超出原有矩形所确定的范围。 思路： 易证， 最终求得的最大矩形的高度一定是某个小矩形的高度。...因此对于每一个高度求出它左右用这个高度可以覆盖到的左右两个位置，用单调栈来计算L[i]和R[i]，相乘后输出最大值即可。...对于每一个小矩形，它能覆盖到的最左面的位置是L[i]，那么L[i]-1位置上的矩形高度一定不会高于或等于H[i]（否则就一定可以向左扩展），最右面的位置是R[i]，那么R[i]+1位置上的矩形高度一定不会高于

    22510

    ​LeetCode刷题实战85： 最大矩形

    题意 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。 样例 ?...这一种在各种图像识别和目标检测算法当中经常用到，模型预测的结果就是图像中心点的坐标以及长宽的长度。 ? 第二种方法可以通过矩形的对角线上的两个点来确定，这种方法只适用于和坐标轴平行的矩形。...我们枚举的复杂度规模这么高是因为我们遍历了所有矩形，遍历矩形本身就是一个时间复杂度开销非常大的举动。如果不想遍历矩形，还有什么方法可以得出最大面积呢？如果我们联想一下上一题很容易得出答案。...在上一题84题当中，题目给出的是一个个竖直类型的矩形，要求这些矩形组合当中能够找到的最大面积。 ?...除了上面提到的之外，还有其他的一些细节，比如数组的创建的长度，还有矩形面积的计算公式等等。很多时候算法之所以难以实现，也正是因为需要考虑的细节很多，整体的逻辑不是非常清楚，需要我们进行大量的思考。

    41420

    201312-3 最大的矩形（Python）

    这n个矩形构成了一个直方图。例如，下图中六个矩形的高度就分别是3, 1, 6, 5, 2, 3。 [01] 请找出能放在给定直方图里面积最大的矩形，它的边要与坐标轴平行。...对于上面给出的例子，最大矩形如下图所示的阴影部分，面积是10。 [02] 【输入格式】 第一行包含一个整数n，即矩形的数量(1 ≤ n ≤ 1000)。...h_i是第i个矩形的高度。 【输出格式】 输出一行，包含一个整数，即给定直方图内的最大矩形的面积。...】 6 3 1 6 5 2 3 【样例1 输出】 10 【解题思路】 把输入数据转化为集合lst_num，防止遍历时重复 遍历lst_num，统计比目前大于或等于num连续值的个数count 和历史最大面积与当前面积...num * count比较，更新最大面积 Notice：更新面积时，可能会把当前num下最后一个连续矩形忘掉 【解题程序】 n = int(input()) lst = list(map(int, input

    1.2K00

    Leetcode No.85 最大矩形（单调栈）

    一、题目描述 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。...[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：6 解释：最大矩形如上图所示...为了计算矩形的最大面积，我们只需要计算每个柱状图中的最大面积，并找到全局最大值 于是，本质上是No.84 柱状图中最大的矩形题中优化暴力算法的复用。...计算 left 矩阵需要 O(mn) 的时间；对每一行应用柱状图算法需要 O(n) 的时间，一共需要 O(mn) 的时间。 空间复杂度：O(mn)，其中 m 和 n 分别是矩阵的行数和列数。...对每个点重复这一过程，就可以得到全局的最大矩形。 我们预计算最大宽度的方法事实上将输入转化成了一系列的柱状图，我们针对每个柱状图计算最大面积。

    29510

    P1719 最大加权矩形

    ，我们还需要运动，于是就决定找校长申请一块电脑组的课余运动场地，听说她们都是电脑组的高手，校长没有马上答应他们，而是先给她们出了一道数学题，并且告诉她们：你们能获得的运动场地的面积就是你们能找到的这个最大的数字...要求矩阵中最大加权矩形，即矩阵的每一个元素都有一权值，权值定义在整数集上。从中找一矩形，矩形大小无限制，是其中包含的所有元素的和最大 。...8 -1 8 0 –2 和为15 几个女孩子有点犯难了，于是就找到了电脑组精打细算的HZH，TZY小朋友帮忙计算，但是遗憾的是他们的答案都不一样，涉及土地的事情我们可不能含糊，你能帮忙计算出校长所给的矩形中加权和最大的矩形吗...输出格式： 最大矩形（子矩阵）的和。...然后每次求最大子段和就好 1 #include 2 #include 3 #include 4 #include 5 using

    826130

    【leetcode刷题】T23-最大矩形

    ["1","1","1","1","1"],   ["1","0","0","1","0"] ] Output:  【中文题目】 给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形...  ["1","0","1","1","1"],   ["1","1","1","1","1"],   ["1","0","0","1","0"] ] 输出:  【思路】 如果明白【T22-柱状图中最大的矩形...】这道题的思路，那么本题的想法就很自然了：对于每一行，将其转换为柱状图，计算最大矩形面积即可。...（柱状图中计算矩形面积，需要使用一个栈，栈顶到栈底元素从大到小，这样每遇到一个比栈顶元素小的元素，则弹出栈，计算矩形面积，返回面积最大值即可。） 本题还可以使用动态规划来完成，待以后刷题时再来解决。...matrix[])         res =          # 对于每一行         for i in range(len(matrix)):             # 更新ls，并计算最大矩形

    44330

    LeetCode 84 | 单调栈解决最大矩形问题

    题意 假设我们有一系列宽度相同都为1的矩形竖直地摆放在一起，请问摆放而成的这个图案所能围成的最大矩形的面积是多少？ ? 比如上图当中，我们有6个矩形，它们的宽度都是1。...我们能找到的最大矩形应该是中间5和6围成的矩形： ? 题目给定一个含有若干个整数的数字，表示这些矩形的高度，要求返回能找到的面积最大的矩形的面积。...最简单的解法就是找出能够围成的所有矩形，然后比较它们之间的面积，得出其中的最大面积。我们很容易可以想到可以遍历矩形的起始位置，这样就得到了矩形的宽。...因为我们只有n个木条，以每个木条为短板寻找最大矩形，那么我们一定可以找出最多n个矩形。...为了找到每个木条对应的最大矩形，我们需要找到每个短板向左以及向右能够延伸到的最远位置。

    99820

    单调栈巧解柱状图最大矩形

    [LeetCode-84] 柱状图中最大的矩形 题目描述 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。 ?...图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。...示例输入 输入: [2,1,5,6,2,3] 输出: 10 如何入手 首先来这么考虑，“能够勾勒出的最大矩形面积” 意味着如果我们可以枚举所有的矩形大小，就可以找到最大的矩形面积。...我为所有的矩形增加编号，让下文的描述更清晰。其实发现的规律就是，5 号矩形高度所围成的最大矩形情况其实是和 2 号矩形相关系的。为什么？...每一次弹栈的矩形是 cur 矩形，由于将要弹出，则进行一次以 cur 矩形高度为准的最大面积矩形的计算。

    1.6K30
    点击加载更多

    扫码

    添加站长 进交流群

    领取专属 10元无门槛券

    手把手带您无忧上云

    扫码加入开发者社群

    相关资讯

    热门标签

    更多标签

    活动推荐

      运营活动

      活动名称
      广告关闭

      腾讯云开发者

      扫码关注腾讯云开发者

      扫码关注腾讯云开发者

      领取腾讯云代金券

      热门产品

      热门推荐

      更多推荐

      Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有

      深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

      腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287

      领券