文章关键词:No.84 Largest Rectangle Histog

No.84 Largest Rectangle in Histogram

作者:神秘网友 发布时间:2021-10-13 07:23:57

No.84 Largest Rectangle in Histogram

84. 柱状图中最大的矩形 - 力扣(LeetCode) (leetcode-cn.com)

现在我们从头开始讲,如果要求只能遍历一次,那么如何求最大面积
我想到一个思路,那就是先把能完全包含各个柱状图的矩形的最大面积求出来,然后求出其中最大值即可。以例题来说就是

能完全覆盖第0个柱子的最大矩形

能完全覆盖第1个柱子的最大矩形


能完全覆盖第2个柱子的最大矩形


能完全覆盖第3个柱子的最大矩形

能完全覆盖第4个柱子的最大矩形

能完全覆盖第5个柱子的最大矩形

 public int largestRectangleArea(int[] heights) {
        int maxNum = heights[0];
        int len = heights.length;
        int[] newheight = new int[len + 2];
        newheight[0] = 0;
        newheight[len + 1] = 0;
        for (int i = 0; i  len; i++) {
            newheight[i + 1] = heights[i];
        }
        heights = newheight;   // 给height数组的首尾各添加一个0
        DequeInteger idx_stack = new ArrayDeque();

        idx_stack.addLast(0);
        for (int i = 1; i = len+1; i++) {
            if (heights[i]  heights[idx_stack.getLast()]) {    // heights[i]比栈顶元素大,则入栈
                idx_stack.addLast(i);
            } else if (heights[i] == heights[idx_stack.getLast()]) {
                idx_stack.removeLast();
                idx_stack.addLast(i);
            } else {  // 当heights[i]的值比栈顶元素的小,则开始计算当前以当前栈顶为高的矩形面积
                while (heights[i]  heights[idx_stack.getLast()]) {
                    int curIdx = idx_stack.getLast();
                    idx_stack.removeLast();   // 只要栈顶元素比将入栈的元素heights[i]要大, 就需要讲其抛出,并计算其面积
                    int right = i;
                    int left = idx_stack.getLast();
                    int width = right - left - 1;
                    maxNum = Math.max(maxNum, width * heights[curIdx]);   //heights中的矩形都以左下角为索引
                }
                idx_stack.addLast(i);
            }
        }
        return maxNum;
    }

如此这般,就能够覆盖所有分支而又不遗漏,将这6个矩形的面积比较下就知道最大面积了。

思路:单调栈,维护一个递增的栈

对于初始的高度数组heights[],遍历其中的元素,按照一定的规则将元素压入栈,规则就是想入栈的元素heights[i],需要比栈顶元素更大,

这是为了给当前的栈顶元素卡住位置,如果想要入栈的heights[i]比栈顶元素要小,那么就可以开始计算栈顶元素为高的最大面积。

注意:heights[]开头和结尾各加一个0,卡住首尾矩阵。最后一轮相当于高度为0的元素一直卡在最后,把前面剩余的单调递增矩阵一波带走。


本文章教程介绍完毕,更多请访问跳墙网其他文章教程!

No.84 Largest Rectangle in Histogram 相关文章

  1. largest-rectangle-in-histogram

    largest-rectangle-in-histogram 【题目描述】Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. For example, Given height =[2,1,5,6,2,3

  2. Leetcode_84 Largest Rectangle in Histogram

    Leetcode_84 Largest Rectangle in Histogram 今天看了看Leetcode_84题,难度是hard,趁着空闲,简单地写一写吧。 原题链接:https://leetcode.com/problems/largest-rectangle-in-histogram/?tab=Description 原题题目: Given n non-negative integers rep

  3. leetcode 84.Largest Rectangle in Histogram

    leetcode 84.Largest Rectangle in Histogram Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Above is a histogram where width of eac

  4. F - Largest Rectangle in a Histogram(单调栈)

    题目地址:https://vjudge.net/contest/424167#problem/F 题目描述: A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the

  5. HDU-1506-Largest Rectangle in a Histogram算法笔记

    HDU-1506-Largest Rectangle in a Histogram算法笔记 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1506 Problem Description: Input: The input contains several test cases. Each test case describes a histogram and starts with an inte

  6. Largest Rectangle in HistogramMaximal Rectangle

    Largest Rectangle in HistogramMaximal Rectangle 题目: Largest Rectangle in Histogram Given n non-negative integers representing the histogram's bar height where the width of each bar is 1, find the area of largest rectangle in the histogr

  7. 703. Kth Largest Element in a Stream

    仅供自己学习 思路: 一开始是想直接sort,然后取出第K大的元素,但是测试数据还会调用add一直加入新元素,如果一直sort会消耗大量时间 另一种就是考虑把第K大后的数都剔除掉,只留下第K大和第K-1,K-2大的数。所以使用一个优...

  8. 515. Find Largest Value in Each Tree Row

    515. Find Largest Value in Each Tree Row 515. Find Largest Value in Each Tree Row Given the root of a binary tree, return an array of the largest value in each row of the tree (0-indexed) . Example 1: Input: root = [1,3,2,5,3,null,9] Output

  9. 【ProjectEuler】8.Largest product in a series 相邻13个数的最

    【ProjectEuler】8.Largest product in a series 相邻13个数的最大乘积 求给出的一串数据中相邻的13个数的最大乘积是多少 原题目如下 从这1000个数据里面找出最大的13个相邻数的乘积 思路 使用滑动窗口暴力求解,窗口大小为13,计算这13...

  10. 【ProjectEuler】11.Largest product in a grid 矩阵中的最大乘

    【ProjectEuler】11.Largest product in a grid 矩阵中的最大乘积 求一个20x20 的矩阵中,相邻的四个数最大乘积 相邻的四个数可以是同一行、同一列或者同一条对角线上 原题目如下 解题思路 首先是处理数据,将矩阵存入二维数组中,这...

  11. Find Largest Value in Each Tree Row宽度优先遍历算法详解

    Find Largest Value in Each Tree Row宽度优先遍历算法详解 问题详见: Find Largest Value in Each Tree Row You need to find the largest value in each row of a binary tree. Example: Input: 1 / \ 3 2 / \ \ 5 3 9 Output: [1, 3, 9] 解题思路: 由题

  12. leetcode NO.84 格雷编码 白痴讲解 腾讯精选练习50

    leetcode NO.84 格雷编码 白痴讲解 腾讯精选练习50 举报了,本来写的好好的,突然没了,什么辣鸡编译器。 今天这个题目不太好懂,看了好几个blog我才看懂是什么,我先来解释一下 关键在于多读几遍这个句,格雷编码是一个二进...

  13. 第十二周算法分析与设计: Find Largest Value in Each Tree Row

    第十二周算法分析与设计: Find Largest Value in Each Tree Row 问题描述: You need to find the largest value in each row of a binary tree. Example: Input: 1 / \ 3 2 / \ \ 5 3 9 Output: [1, 3, 9] 解法思路: 跟第十周的算法思路类似,在 层次遍历

  14. Halcon算子smallest_rectangle1()和smallest_rectangle2()

    Halcon算子:smallest_rectangle1()和smallest_rectangle2() Halcon 算子 : smallest_rectangle1() 和 smallest_rectangle2() smallest_rectangle1(Regions : : : Row1, Column1, Row2, Column2) 功能: 返回平行坐标最小外包矩形 该算子计算返回输入区域的平

  15. Matplotlib - histogram(频数分布)

    Matplotlib - histogram(频数分布) title: Matplotlib - histogram(频数分布) categories: Matplotlib tags: python Matplotlib Computer Drawing 主要内容:histogram函数 numpy.histogram() 函数是数据的频率分布的图形表示。 水平尺寸相等的矩形对应于

  16. Image Processing(Histogram)

    Image Processing(Histogram) 【代码过程】 1.读入俩张灰度图 2.对俩张图片分别进行均衡化 def histequ(gray, nlevels=256): # Compute histogram # np.bincount compute the amount of each pixel histogram = np.bincount(gray.flatten(), minlength=nlev

  17. 矩形Rectangle

    矩形Rectangle 题目 我怎么这么菜啊 思路题解 以为可以用扫描线扫,但是发现这些点不连续,没有多想 ,就去看题解了 首先扫描线扫坐标,先确定右端线,然后在从右往左确定左端的线,边扫边加点,那么矩形左右已经确定了,...

  18. [R]直方(Histogram)的用法

    [R]直方(Histogram)的用法 直方(Histogram)常用於分布和分的呈功能。在R言中,利用hist指令即可,同亦可出分布果,法明如下。 Histograms Description: The generic function hist computes a histogram of the given data v

  19. Python 之 histogram直方图

    Python 之 histogram直方图 iris.csv Histogram import matplotlib.pyplot as pltimport pandas as pdiris_df = pd.read_csv(iris.csv)iris_df[sepallength].hist(by=iris_df[class]) #Group data by class labelplt.show() Stacked histogram 堆叠直方图 imp

  20. 碰撞检测 :Rectangle

    碰撞检测 :Rectangle 在 Collision Detection :Point 中主要介绍了点的碰撞检测,接着来看看矩形的情况。 以下示例未做兼容性检查,建议在最新的 Chrome 浏览器中查看。 Origin My GitHub 这是示例页面。 绘制矩形可以通过四个点的坐标进...

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2021, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词