您好、欢迎来到现金彩票网!
当前位置:秒速牛牛投注 > 桶链算法 >

【搞定算法】单调栈问题:直方图中的最大矩形面积、求最大子矩阵

发布时间:2019-08-19 01:23 来源:未知 编辑:admin

  1、新元素加入栈前,会在栈顶端把破坏栈单调性的元素都删除,直到栈为空或者栈满足单调性才能加入新元素;

  2、单调栈是 O(N) 级的时间复杂度,所有元素只会进入栈一次,并且出栈后再也不会进栈;

  3、单调栈可以找到元素向左遍历第一个比它小(大)的元素,也就是说在元素进栈前它向左拓展的区间已经确定,在出栈前它能向右拓展的区间也能确定(左区间好理解,仔细体会右区间的确定,若该元素至遍历结束后也未出栈,那么就是说在原数组中,该元素的右方向没有一个元素可以比它大/小,那么该元素的右边界就是原数组的大小(就是没有右边界),否则它的右边界就是令它出栈的元素)。

  有重复元素时,只需要在每个位置拉一个链表出来就行了。每次插入元素都是插入到链表的尾部,这样任一元素左边比它小的最近的元素就是栈中左边位置链表的尾元素。

  问题:直方图是由排列在同一基线上的一系列矩形组成的多边形。为了简单起见,假设这些矩形的宽度相等但高度可能不同。例如,下图1给出了一个直方图,其中各个矩形的高度为3、2、5、6、1、4、4,宽度为标准1单位。当给定了一个保存所有矩形高度的数组时,如何找到其中最大的矩形。

  考虑必须包含某个柱子的矩形的最大面积,那么我们就需要找到这个柱子往左和往右的边界,这样宽度高度都有了,就有了必须包含这个柱子的最大面积,左右柱子的这个最大面积求出来,这其中的最大即为全局最大。

  1、使用一个stack,首先压入第一个元素的位置,然后遍历数组,在遇到当前数组大于栈顶对应值时,直接入栈即可,否则进行出栈操作,直到栈顶元素的值小于当前元素。然后压入当前元素。这一过程中即可求出必须包含栈顶元素的最大矩阵面积。

  假设现在遍历到 i,如果栈顶元素小于 heights[i],表明这个 i 就是栈顶元素的左边界,而栈顶元素的右边界就是栈顶元素的下边一个元素(为空补 -1),这样就可以求得必须包含栈顶元素的最大矩形面积。这样遍历一次之后就所有的情况都考虑到了。需要注意的是你遍历结束之后,可能栈中还有元素,也需要把这些元素弹出结算,此时这些元素的右边界即为heights.length。

  题目:给定一个整型矩阵 map,其中的值只有 0 和 1 两种,求其中全是 1 的所有矩形区域中,最大的矩形区域为 1 的数量。

  1、算出必须以第 i 行作为底的情况下的直方图高度是多少【从当前位置出发,往上有多少个连续的 1】

  2、算出该直方图的最大矩形面积:单调栈问题,只是多了个等号,用上面那种 list 来解决重复也可以,只是这种更简单【相等也会让栈弹出,那么以该值为底的最大矩形是让它弹出那个相等的说了算】

  2.如果 A 和 B 是不同的山,并且在环中相邻,认为可以相互看见。比如图1-8 中,相邻的山峰对有(1,2)(2,4)(4,5)(3,5)(1,3)。

  3.如果 A 和 B 是不同的山,并且在环中不相邻,假设两座山高度的最小值为min。如果A通过next 方向到B 的途中没有高度比min 大的山峰,或者 A 通过last 方向到 B 的途中没有高度比 min 大的山峰,认为 A 和 B 可以相互看见。比如图中,高度为 3 的山和高度为 4 的山,两座山的高度最小值为 3。3 从 last 方向走向 4,中途会遇见 5,所以 last 方向走不通;3 从 next 方向走向4,中途会遇见1 和 2,但是都不大于两座山高度的最小值 3,所以 next 方向可以走通。

  有一个能走通就认为可以相互看见。再如,高度为 2 的山和高度 为5 的山,两个方向上都走不通,所以不能相互看见。图中所有在环中不相邻,并且能看见的山峰对有(2,3)、(3,4)。给定一个不含有负数且没有重复值的数组 arr,请返回有多少对山峰能够相互看见。

  进阶问题:给定一个不含有负数但可能含有重复值的数组 arr,返回有多少对山峰能够相互看见。

  如果 arr 长度为N,没有重复值的情况下时间复杂度达到 O(1),可能有重复值的情况下时间复杂度请达到 O(N)。

  原问题:时间复杂度 O(1) 的解。如果数组中所有的数字都不一样,可见山峰对的数量可以由简单公式得到。环形结构中只有1 座山峰时,可见山峰对的数量为 0;环形结构中只有2 座山峰时,可见山峰对的数量为1。这都是显而易见的。环形结构中有 i 座山峰时(i 2),可见山峰对的数量为 2 × i - 3。下面给出证明。

  我们只用高度小的山峰去找高度大的山峰,而永远不用高度大的山峰去找高度小的山峰【精髓】。比如题目描述中的例子,从 2 出发按照“小找大”原则,会找到 (2,3) 和 (2,4),但是不去尝试2能不能看到 1,因为这是“大找小”,而不是“小找大”。(1,2) 这一对可见山峰不会错过,因为从 1 出发按照“小找大”原则找的时候会找到这一对。从每一个位置出发,都按照“小找大”原则找到山峰对的数量,就是总的可见山峰对数量。

  环形结构中只有 1 座山峰时,可见山峰对的数量为0;环形结构中只有2座山峰时,可见山峰对的数量为 1。这都是显而易见易见的。

  因为 i 座山峰高度不一样,必然在环中存在唯一的最大值和唯一的次大值(第二大的值)。x 是除了最高值和次高值之外的任何一座山峰,所以 x 在 last 方向上必存在第一个高度比它大的节点,x 在 next 方向上也必存在第一个高度比它大的节点,所以从 x出发能找到且只能找到 2 对。

  除了最大值和次大值之外还剩 i - 2 个节点,这 i - 2 个节点每一个都能找到 2 对,所以一共有(i - 2) *2 对,还有 1 对,就是次大值能够看见最大值这对。所以一共是 2i - 3 对。

  1、首先遍历一次环形山结构,找到最大值的位置,如果最大值不只一个,找哪一个最大值都行。准备一个栈,栈中放 stack,Record 包含元素及元素目前重复了多少个;

  2、求一个数左边(逆时针方向)离它最近的比它大的数,右边(顺时针)离它最近的比它大的数,然后他们就能和该数组成可见山峰对。栈中按从栈底到栈顶由大到小的顺序放入,不满足就弹出栈顶元素,说明找到了栈顶元素的可见山峰,然后计算可见山峰对;

  求图片中矩形最大的面积,类似于桶的容量由最短的木板决定的,见图片。  矩形的高度可以用数组表示,同时这个场景可以和另外一个场景联系起来:给定一个二维矩阵,矩阵中的元素只有0和1,求一个最大的子矩阵(要...博文来自:liurong_scut的博客

  直方图最大面积时间限制:1sec空间限制:256MB问题描述有一个直方图,横轴长度为n,第i列的高度为h[i]。请你求出在这个直方图中面积最大的子矩阵。输入格式第一行一个正整数n。第二行n个用空格隔开...博文来自:的博客

  单调栈,顾名思义就是说栈内的元素,按照某种方式排序下,必须是单调的。如果新入栈的元素破坏了单调性,就弹出栈内元素,直到满足单调性。它可以很方便地求出某个数的左边或者右边第一个比它大或者小的元素,而且总...博文来自:say_haha的博客

  题目:有N个矩形,宽度都为1,给出N个矩形的高度,求由这N个矩形组成的图形包含的最大的矩形面积。分析:对于每个矩形,我们求出它向左向右分别能延伸的长度,然后乘以它的高度,这就是以当前矩形为最低高度可以...博文来自:Broken_Wave的博客

  给定一组非负整数组成的数组,代表一组柱状图的高度,其中每个柱子的宽度都是1.在这组柱状图中找到能组成的最大矩形的面积。#includeusingnamespacestd;intmain(intargc...博文来自:liuyongli1992的博客

  一个直方图是由许多矩形组成,在给定的直方图中找出最大的矩形面积。输入:输入包含若干测试用例。每个测试用例描述直方图,并开始与整数n,表示它由组成的矩形的数量。你可以假设那1然后按照n个整数h1,......博文来自:wanghuanhuabb的博客

  求直方图中的最大矩形面积:例如给定直方图{2,3,1,2,4,2}则直方图中最大矩形面积为x=(3,6),x=3,y=2,max面积=6思考:利用枚举法/*当前位置往前进行枚举法*/publicc...博文来自:gaven的博客

  题目:给定一个整型矩阵map,其中的值只有0和1两种,求其中全是1的所有矩形区域中,最大的矩形区域为1的数量。例如:0其中,最大的矩形区域有6个1,所以返回6。思路:参考左神pu...博文来自:的博客

  题目链接题目给一个向量,里面存一个序列,表示一个直方图的各个元素高,要求出这个直方图中的最大矩形面积;构建一个递增的单调栈:[单调栈就是一个栈,栈底元素向栈头元素递增,新加入的元素如果小于栈顶元素,就...博文来自:的博客

  单调队列和单调栈很相似,他们是什么区别呢?首先引用的话:单调栈解决的是以某个值为最小(最大)值的...博文来自:roufoo的博客

  题目题目传送门题目传送门题目传送门题解如果矩形的高度从左向右单调递增,那么我们可以枚举每个矩形的高度,并把宽度延伸到左右边界,来计算面积,从中取得最大值来得到答案。但实际上矩形高度不可能是单调递增的。...博文来自:MILLOPE的博客

  求最大子矩阵的大小(题目)给定一个整型矩阵map,其中的值只有0和1两种,求其中全是1的所有矩形区域中,最大的矩形区域为1的数量。例如:1110其中,最大的矩形区域有3个1,所以返回3。再如:1011...博文来自:Amber的博客

  题目是英文的…这里简单描述一下,就是给你n个宽度1的矩形,然后连在一排,求新组成的图形中的最大矩形.单调栈维护一个高度单调递增的栈,每个新数经来的时候要是比栈顶元素小的话就弹出栈顶元素直到不能再弹为止...博文来自:Le Petit Prince

  【题目链接】         点击打开链接【题意】         给了一些h*w的矩形,大小可不等,求可组成的最大矩形面积是多少?单调栈经典题,做法和点击打开链接完全相同。【AC代码】////Cre...博文来自:I good vegetable a!

  原题链接1158 全是1的最大子矩阵基准时间限制:1 秒空间限制:131072 KB分值: 80 难度:5级算法题 收藏 关注给出1个M*N的矩阵M1,里面的元素只有0或1,找出M1的一个子矩阵M2,...博文来自:L.

  求最大子矩阵的大小给定一个整型矩阵map,其中的值只有0和1两种,求其中全是1的所有矩形区域中,最大的矩形区域为1的数量。例如:1110其中,最大的矩形区域有3个1,所以返回3。再如:10111111...博文来自:weixin_30915951的博客

  这道题的唯一的难点是:二维转化成一维的时候: /*如果当前行j位仍然是1,那么height[j]++。否则height[j]更新为0*/  比如第一列上一行是.,第二行第一列是X,那肯定...博文来自:的博客

  点击打开题目1102 面积最大的矩形基准时间限制:1 秒空间限制:131072 KB分值: 20 难度:3级算法题 收藏 关注有一个正整数的数组,化为直方图,求此直方图包含的最大矩形面积。例如2,1,...博文来自:离殇灬孤狼

  (1)问题描述:直方图中最大矩形面积,一个直方图是有许多矩形组成的,在给定的直方图中找出最大的矩形面积,为了简化,假定所有矩形的宽为1。(2)直方图最大面积的算法理解:   1、将一个起伏的直方图分解...博文来自:的博客

  直方图中最大矩形((LargestRectangleinHistogram))问题:直方图是由排列在同一基线上的一系列矩形组成的多边形。为了简单起见,假设这些矩形的宽度相等但高度可能不同。例如,下图1...博文来自:q2nAmor

  在下图的七个矩形所占的位置中找出一个最大的矩形,如下所示,红框中所框出的就是这个直方图的最大矩形,面积为12。最直观且笨拙的解法是枚举(n+1)n/2(n+1)n/2个区间然后利用线段树做RMQ查询区...博文来自:remixone

  给定直方图,每一小块的height由N个非负整数所确定,每一小块的width都为1,请找出直方图中面积最大的矩形。 如下图所示,直方图中每一块的宽度都是1,每一块给定的高度分别是[2,1,5,6,2,3]: 那么上述直方图中,...

  由于个人原因,上次上传的是练习的,有写问题,这是自己修改后的... 直方图中每一块的宽度都是1,每一块给定的高度分别是[2,1,5,6,2,3]; 那么上述直方图中,面积最大的矩形面积 = 10单位

  在X轴上水平放置着N个条形图,这N个条形图就组成了一个柱状图,每个条形图都是一个矩形,每个矩形都有相同的宽度,均为1单位长度,但是它们的高度并不相同

  1、使用暴力算法枚举所有的端点计算其最小值,复杂度为O(n2)O(n2)O(n^2)2、观察特点,很多区间的左边和右边其实还可以拓展,产生更大的面积3、拓展的边界就是第一个小于这个原始区间中最小的那个...博文来自:ProJ7-Jeffy

  POJ2559  这是最基本的,宽度都为1,只需考虑高度即可。对于每个矩形,我们从它往左开始找到第一个高度小于它的,记找到的左界为Li,同理,找到的右界为Ri,则以这个举行为基准找到的最大矩形面积为H...博文来自:Interstellar_的博客

  以i所指的矩形高度作为要组成的矩形的高度,分别向左右扩展。用单调栈维护一个left数组和一个right数组,记录向左右能扩展到的边界,然后扫一遍出结果。#include#include#include...博文来自:梦幻的蔷薇色

  【题目描述】:地面上从左到右并排紧挨着摆放多个矩形,已知这此矩形的底边宽度都为1,高度不完全相等。求在这些矩形包括的范围内能得到的面积最大的矩形,打印出该面积。所求矩形可以横跨多个矩形,但不能超出原有...博文来自:LvYanchang的博客

  题目:题意:分析:这题及得好像在哪做过QAQ,很快就水掉了,刚开始想...博文来自:HARD_UNDERSTAND

  刷题的时候发现搞不定看了好多文档发现写的都不是很清楚,后来终于想明白了。关键是...博文来自:u011150728的博客

  01矩阵最大正方形面积题意:给定一个矩阵,其中的元素为0或者1,要求找出其中元素全为1的面积最大的正方形。题解:动态规划:对每个元素,把以其为右下角,元素全为1的正方形的最长边长记录下来。如果以元素a...博文来自:ArcherLu的博客

  题目描述有一个直方图,用一个整数数组表示,其中每列的宽度为1,求所给直方图包含的最大矩形面积。比如,对于直方图[2,7,9,4],它所包含的最大矩形的面积为14(即[7,9]包涵的7x2的矩形)。给定...博文来自:FzuGsr的专栏

  时间限制:1sec空间限制:256MB问题描述有一个直方图,横轴长度为n,第i列的高度为h[i]。请你求出在这个直方图中面积最大的子矩阵。输入格式第一行一个正整数n。第二行n个用空格隔开的非负整数,依...博文来自:ACM_JURUO

  一个直方图是由许多矩形组成,在给定的直方图中找出最大的矩形面积。同时,为了简化问题,假定所有矩形宽度都为1个单位。例如,下面的直方图中有6个矩形,高度分别是(6,7,8,4,5,3)。最大的矩形面积是...博文来自:serena_0916的博客

  Leetcode编程练习二:求直方图中矩形最大面积博文来自:ether_crow的博客

  授予每个自然周发布1篇到3篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。

  TA的个人主页

  【搞定算法】找出数组中只出现一次的那个数,其他都出现两次【字节跳动面试题】

  【LeetCode】第538题:把二叉搜索树转换为累加树(百度面试题)

http://duchtech.com/tongliansuanfa/490.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有