【力扣】84. 柱状图中最大的矩形 <模拟、双指针、单调栈>

这篇具有很好参考价值的文章主要介绍了【力扣】84. 柱状图中最大的矩形 <模拟、双指针、单调栈>。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【力扣】84. 柱状图中最大的矩形

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。求在该柱状图中,能够勾勒出来的矩形的最大面积。

示例 1:
【力扣】84. 柱状图中最大的矩形 <模拟、双指针、单调栈>,力扣及OJ,# 栈、队列、单调栈,# 双指针,leetcode,java,算法

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

示例 2:
【力扣】84. 柱状图中最大的矩形 <模拟、双指针、单调栈>,力扣及OJ,# 栈、队列、单调栈,# 双指针,leetcode,java,算法

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

提示:
1 <= heights.length <= 1 0 5 10^5 105
0 <= heights[i] <= 1 0 4 10^4 104

题解

暴力求解
public static int largestRectangleArea(int[] heights) {
    int sum = 0;
    for (int i = 0; i < heights.length; i++) {
        int left = i;
        int right = i;

        //找当前遍历元素之前第一个比它小的元素
        while (left >= 0) {
            if (heights[left] < heights[i]) {
                break;
            }
            left--;
        }

        //找当前遍历元素之后第一个比它小的元素
        while (right < heights.length) {
            if (heights[right] < heights[i]) {
                break;
            }
            right++;
        }

        int w = right - left - 1;
        int h = heights[i];
        sum = Math.max(sum, w * h);
    }
    return sum;
}
双指针
public class Solution {
    public static 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 t = i - 1;
            // 这里不是用if,而是不断向右寻找的过程
            while (t >= 0 && heights[t] >= heights[i]) {
                t = minLeftIndex[t];
            }
            minLeftIndex[i] = t;
        }


        // 记录每个柱子右边第一个小于该柱子的下标
        minRightIndex[heights.length - 1] = heights.length;
        for (int i = heights.length - 2; i >= 0; i--) {
            int t = i + 1;
            while (t < heights.length && heights[t] >= heights[i]) {
                t = minRightIndex[t];
            }
            minRightIndex[i] = t;
        }

        /*for (int a : minLeftIndex) {
            System.out.println(a);
        }
        System.out.println("______________________________");

        for (int a : minRightIndex) {
            System.out.println(a);
        }*/

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

    public static void main(String[] args) {
        int[] heights = {2, 4, 2};
        System.out.println(largestRectangleArea(heights));
    }
}
单调栈

注意:单调栈是递减的文章来源地址https://www.toymoban.com/news/detail-661359.html

class Solution {
    int largestRectangleArea(int[] heights) {
        Stack<Integer> st = new Stack<Integer>();
        
        // 数组扩容,在头和尾各加入一个元素,防止只递增或者只递减的数组
        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];
        }

        heights = newHeights;
        
        st.push(0);
        int result = 0;
        // 第一个元素已经入栈,从下标1开始
        for (int i = 1; i < heights.length; i++) {
            // 注意heights[i] 是和heights[st.top()] 比较 ,st.top()是下标
            if (heights[i] > heights[st.peek()]) {
                st.push(i);
            } else if (heights[i] == heights[st.peek()]) {
                st.pop(); // 这个可以加,可以不加,效果一样,思路不同
                st.push(i);
            } else {
                while (heights[i] < heights[st.peek()]) { // 注意是while
                    int mid = st.peek();
                    st.pop();
                    int left = st.peek();
                    int right = i;
                    int w = right - left - 1;
                    int h = heights[mid];
                    result = Math.max(result, w * h);
                }
                st.push(i);
            }
        }
        return result;
    }
}

到了这里,关于【力扣】84. 柱状图中最大的矩形 <模拟、双指针、单调栈>的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 算法leetcode|84. 柱状图中最大的矩形(rust重拳出击)

    给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。 1 = heights.length =10 5 0 = heights[i] = 10 4 面对这道算法题目,二当家的再次陷入了沉思。 眼睛一看似乎有思路,但是一动手就容易不知

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

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

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

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

    2023年04月19日
    浏览(69)
  • 【算法练习Day51】柱状图中最大的矩形

    ​📝个人主页:@Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:练题 🎯 长路漫漫浩浩,万事皆有期待 力扣题目链接 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩

    2024年01月22日
    浏览(43)
  • OJ练习第101题——柱状图中最大的矩形

    力扣链接:84. 柱状图中最大的矩形 给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。 求在该柱状图中,能够勾勒出来的矩形的最大面积。 我们先嵌套一层 while 循环来向左找到第一个比柱体 i 高度小的柱体,这个过程是 O(N) 的; 单调

    2024年02月04日
    浏览(35)
  • 算法刷题Day 60 柱状图中的最大矩阵

    暴力解法 超时了 分别找出当前位置左边 第一个 比自己小的索引(的后一个位置)和右边 第一个 比自己小的索引(的前一个位置),这个范围之内,就是以当前位置的高度所能达到的最大宽度。 单调栈 有了接雨水那道题的经验,这一道题可以模仿着做出了

    2024年02月14日
    浏览(55)
  • Rust每日一练(Leetday0029) 柱状图、最大矩形、扰乱字符串

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

    2024年02月09日
    浏览(48)
  • 【力扣】496. 下一个更大元素 I <单调栈、模拟>

      nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。给你两个没有重复元素的数组 nums1 和 nums2 ,下标从 0 开始计数,其中nums1 是 nums2 的子集。   对于每个 0 = i nums1.length ,找出满足 nums1[i] == nums2[j] 的下标 j ,并且在 nums2 确定

    2024年02月12日
    浏览(39)
  • 单调栈练习(四)— 统计全 1 子矩形

    题目 同样的LeetCode原题:题目链接 给你一个 m x n 的二进制矩阵 mat ,请你返回有多少个 子矩形 的元素全部都是 1 。 单调栈 解题思路整体和上一篇文章差不多,都是用到了 压缩数组 的技巧,通过压缩数组来构建一个数组矩阵、以每一行为底, 每一列作为矩阵的高度,区别

    2024年01月24日
    浏览(44)
  • Echarts—X轴鼠标滑动或者缩放/多列柱状图中某一列数据为0时不占位

    用柱状图展示12个月的项目对应的供应商数据; 每个月有多个项目不确定,1-50之间,也就是说,12个月,每个月的X轴上有不确定的柱状;例如:1月有20根柱子,2月有5根柱子,3月有15根… 每月的每根柱子代表是一个项目,鼠标移入每月的每一个项目的柱子上要悬浮展示该月该

    2024年02月09日
    浏览(90)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包