直方图下最大矩形问题 o(n) 解对吗？ - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 直方图下最大矩形问题 o(n) 解对吗？

相关主题
● 白板代码，直方图包含的最大矩形面积	● 问问题，0/1 矩阵内最大1矩阵的问题
● 解一道 GOOGLE 面试题 ...	● 刚刚onsite G家，发面经求祝福
● 问一个题	● 直方图盛水最大容量问题
● 一个老面试题	● 求Leetcode OJ Maximal Rectangle的n^2解法
● 明天onsite却发现好多还没掌握啊	● 面试题请教：一个矩阵，里面的值是0或1，找出最大子矩阵，此子矩阵的值全为1
● 最近大公司的面试题有不再偏难的趋势	● 一道老题
● ooyala，apple，ebay面经	● 这道设计面试题这样解对吗
● 顶风作案，Google面经	● google面试题回馈

相关话题的讨论汇总
话题: 矩形话题: 解对话题: 出栈

进入JobHunting版参与讨论

(共1页)

m**a
发帖数: 139

搜索了一下，o(n)的解用stack来做，很多地方有解释：比如：
http://wansishuang.appspot.com/?p=3002
这个算法对2,2,2,4,3对吗？
他只算出栈时候高度为出栈柱子的矩形，这个例子里最大矩形是2,2,2,2,2 形成的。如
果有以上算法的话，应该得不到吧？还是我漏了什么？

(共1页)

进入JobHunting版参与讨论

相关主题
● google面试题回馈	● 明天onsite却发现好多还没掌握啊
● 总结一道题	● 最近大公司的面试题有不再偏难的趋势
● 再问问那个《最大直方图》的经典名题	● ooyala，apple，ebay面经
● 问一个算法设计问题	● 顶风作案，Google面经
● 白板代码，直方图包含的最大矩形面积	● 问问题，0/1 矩阵内最大1矩阵的问题
● 解一道 GOOGLE 面试题 ...	● 刚刚onsite G家，发面经求祝福
● 问一个题	● 直方图盛水最大容量问题
● 一个老面试题	● 求Leetcode OJ Maximal Rectangle的n^2解法

相关话题的讨论汇总
话题: 矩形话题: 解对话题: 出栈

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天