【算法练习Day51】柱状图中最大的矩形

这篇具有很好参考价值的文章主要介绍了【算法练习Day51】柱状图中最大的矩形。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【算法练习Day51】柱状图中最大的矩形,练题,算法

​📝个人主页:@Sherry的成长之路
🏠学习社区:Sherry的成长之路(个人社区)
📖专栏链接:练题
🎯长路漫漫浩浩,万事皆有期待

柱状图中最大的矩形

力扣题目链接

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

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

示例 1:

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

示例 2:

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

思路

接雨水 中是找每个柱子左右两边第一个大于该柱子高度的柱子,而本题是找每个柱子左右两边第一个小于该柱子的柱子。

为什么这么说呢,因为如下图所示,高为3的柱子可以继续往右边蔓延扩大面积,如果往左边的话则长度不够
【算法练习Day51】柱状图中最大的矩形,练题,算法

所以要找当前柱子i左右两侧第一个小于他的柱子

动态规划

对于下标i而言,能勾勒出的最大面积是什么?

以i为中心, 向左寻找第一个小于height[i]的下标minLeftIndex, 向右寻找第一个小于height[i]的下标minRightIndex, 即最大面积 = height[i] * (minRightIndex - minLeftIndex - 1)

如示例1中,求i=4的最大面积
【算法练习Day51】柱状图中最大的矩形,练题,算法

正向遍历数组 height 得到数组 minLeftIndex的每个索引值(第一小于当前柱子高度的索引值),反向遍历数组 height 得到数组minRightIndex(第一小于当前柱子高度的索引值)

完整代码:

public int largestRectangleArea(int[] heights) {
    int[] minLeftIndex = new int[heights.length];
    int[] minRightIndex = new int[heights.length];

    // 记录每个柱子 左边第一个小于该柱子的下标
    minLeftIndex[0] = -1;
    for (int i = 1; i < heights.length; i++) {
        int left = i - 1;
        // 这里不是用if,而是不断向左寻找的过程
        while (left >= 0 && heights[left] >= heights[i]) {
            left = minLeftIndex[left];
        }
        minLeftIndex[i] = left;
    }

    // 记录每个柱子 右边第一个小于该柱子的下标
    minRightIndex[heights.length - 1] = heights.length;
    for (int i = heights.length - 2; i >= 0; i--) {
        int right = i + 1;
        // 这里不是用if,而是不断向右寻找的过程
        while (right < heights.length && heights[right] >= heights[i]) {
            right = minRightIndex[right];
        }
        minRightIndex[i] = right;
    }

    // 求和
    int res = 0;
    for (int i = 0; i < heights.length; i++) {
        int sum = heights[i] * (minRightIndex[i] - minLeftIndex[i] - 1);
        res = Math.max(sum, res);
    }
    return res;
}

单调栈

本题是找每个柱子左右两边第一个小于该柱的柱子。这里就涉及到了单调栈很重要的性质,就是单调栈里的顺序,是从小到大还是从大到小。

在题解 接雨水 中接雨水的单调栈从栈头(元素从栈顶弹出)到栈底的顺序应该是从小到大的顺序。

那么因为本题是要找每个柱子左右两边第一个小于该柱子的柱子,所以从栈顶到栈底的顺序应该是从大到小的顺序!

如图所示的例子
【算法练习Day51】柱状图中最大的矩形,练题,算法

当我们遍历到height[5]时,因为栈顶到栈底是从大到小,height[5]高度是小于栈顶元素的,所以就找到了此时的栈顶元素的左右第一个小于的柱子

【算法练习Day51】柱状图中最大的矩形,练题,算法

此时大家应该可以发现其实就是栈顶和栈顶的下一个元素以及要入栈的三个元素组成了我们要求最大面积的高度和宽度

剩下就是分析清楚如下三种情况:

情况一:当前遍历的元素heights[i]小于栈顶元素heights[st.top()]的情况
情况二:当前遍历的元素heights[i]等于栈顶元素heights[st.top()]的情况
情况三:当前遍历的元素heights[i]大于栈顶元素heights[st.top()]的情况
完整代码:

public int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new LinkedList<>();
    // 数组扩容,在头和尾各加入一个元素
    int [] newHeights = new int[heights.length + 2];
    newHeights[0] = 0;
    newHeights[newHeights.length - 1] = 0;
    for (int index = 0; index < heights.length; index++){
        newHeights[index + 1] = heights[index];
    }

    // 之后就用newHeights计算
    stack.push(0);
    int res = 0;
    // 第一个元素已经入栈,从下标1开始
    for (int i = 1; i < newHeights.length; i++) {
        if (newHeights[i] > newHeights[stack.peek()]) {
            stack.push(i);
        }else if (newHeights[i] == newHeights[stack.peek()]) {
            stack.pop();
            stack.push(i);
        }else {
            // 我们要找到一个不小于newHeights[i]为止
            while (newHeights[i] < newHeights[stack.peek()]) {
                int mid = stack.peek(); // 中间柱子
                stack.pop();
                int left = stack.peek();
                int right = i;
                int w = right - left - 1;
                int h = newHeights[mid];
                res = Math.max(res, w * h);
            }
            stack.push(i);
        }
    }

    return res;
}

总结:

今天我们完成了柱状图中最大的矩形这道题,相关的思想需要多复习回顾。接下来,我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。

当然,本文仍有许多不足之处,欢迎各位小伙伴们随时私信交流、批评指正!我们下期见~

【算法练习Day51】柱状图中最大的矩形,练题,算法文章来源地址https://www.toymoban.com/news/detail-814026.html

到了这里,关于【算法练习Day51】柱状图中最大的矩形的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • ● 84.柱状图中最大的矩形

     84.柱状图中最大的矩形

    2024年02月11日
    浏览(41)
  • LeetCode 84. 柱状图中最大的矩形

    84. 柱状图中最大的矩形 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。 示例 1: 输入: heights = [2,1,5,6,2,3] 输出: 10 解释: 最大的矩形为图中红色区域,面积为 10 示例 2: 输入

    2024年02月03日
    浏览(32)
  • (力扣记录)84. 柱状图中最大的矩形

    数据结构类型: 栈 时间复杂度: O(N) 空间复杂度: O(N) 代码实现:

    2024年01月20日
    浏览(36)
  • 【力扣】84. 柱状图中最大的矩形 <模拟、双指针、单调栈>

    给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积。 示例 1: 输入:heights = [2,1,5,6,2,3] 输出:10 解释:最大的矩形为图中红色区域,面积为 10 示例 2: 输入: heights = [2,4] 输出: 4 提示

    2024年02月12日
    浏览(67)
  • 吃透单调栈(2)——解两道Hard题:接雨水、柱状图中最大的矩形问题

    这类题目的数据通常是一维数组,要寻找任一个元素的 右边或者左边 第一个 比自己 大 或者 小 的元素的位置(寻找 边界 ) ,此时我们就要想到可以用单调栈了。   这道题就是要求解每一个柱子左边第一个比它高的柱子,以及右边第一个比它高的柱子,然后这两个柱子间

    2024年02月10日
    浏览(35)
  • LeetCode热题HOT100:76. 最小覆盖子串,84.柱状图中最大的矩形、96. 不同的二叉搜索树

    题目 :给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 “” 。 注意: 对于 t 中重复字符,我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。 如果 s 中存在这样的子串,我们保

    2023年04月19日
    浏览(56)
  • Rust每日一练(Leetday0029) 柱状图、最大矩形、扰乱字符串

    目录 84. 柱状图中最大的矩形 Largest-rectangle-in-histogram  🌟🌟🌟 85. 最大矩形 Maximal Rectangle  🌟🌟🌟 87. 扰乱字符串 Scramble String  🌟🌟🌟 🌟 每日一练刷题专栏 🌟 Rust每日一练 专栏 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一练 专栏 Java每日一练 专栏 给定  n

    2024年02月09日
    浏览(46)
  • 每天一道算法练习题--Day22&& 第一章 --算法专题 --- ----------最大公约数

    关于最大公约数有专门的研究。 而在 LeetCode 中虽然没有直接让你求解最大公约数的题目。但是却有一些间接需要你求解最大公约数的题目。 时间复杂度:最好的情况是执行一次循环体,最坏的情况是循环到 smaller 为 1,因此总的时间复杂度为 O ( N ) O(N) O ( N ) ,其中 N 为 a 和

    2024年02月03日
    浏览(53)
  • 【算法奥义】最大矩形问题

    下面展示 cpp代码 。

    2024年02月10日
    浏览(43)
  • 面试算法40:矩阵中的最大矩形

    请在一个由0、1组成的矩阵中找出最大的只包含1的矩形并输出它的面积。例如,在图6.6的矩阵中,最大的只包含1的矩阵如阴影部分所示,它的面积是6。 直方图是由排列在同一基线上的相邻柱子组成的图形。由于题目要求矩形中只包含数字1,因此将矩阵中上下相邻的值为1的

    2024年02月06日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包