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 each bar is 1, given height = [2,1,5,6,2,3]
.
The largest rectangle is shown in the shaded area, which has area = 10
unit.
For example,
Given height = [2,1,5,6,2,3]
,
return 10
.
Solution 1:
Brute force. O(n^2). 运行大集合时会超时。
public int largestRectangleArea(int[] height) { int n = height.length; int maxArea = 0; for(int i=0; i<n; i++) { int minHeight = height[i]; for(int j=i; j<n; j++) { minHeight = Math.min(minHeight, height[j]); maxArea = Math.max(maxArea, (j-i+1)*minHeight); } } return maxArea; }
Solution 2:
用Stack来处理,Stack内保存的是非递减的高度的索引。
public int largestRectangleArea(int[] H) { int n = H.length; int maxArea = 0, i = 0; Stack<Integer> stack = new Stack<>(); while(i <= n) { int h = (i == n) ? 0 : H[i]; if(stack.isEmpty() || h >= H[stack.peek()]) { stack.push(i++); } else { int j = stack.pop(); int area = (stack.isEmpty() ? i : i-1-stack.peek()) * H[j]; maxArea = Math.max(maxArea, area); } } return maxArea; }
相关推荐
LeetCode题目Largest Rectangle in Histogram 解答
大佬的leetcode刷题笔记(c++版本)
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
leetcode 答案Leetcode---数据库 我对 Leetcode 数据库问题的回答
LeetCode题解 - Java语言实现-181页.pdf
LeetCode-Solutions-in-Swift.zip,swift 5中的leetcode解决方案
彩色版本 正版 pdf 精讲数据结构 + 算法 链表 树 图表 贪心算法 指针 动态规划 查找算法
leetcode1-300.docx
leetcode 答案leetcode--python Leetcode 的答案
leetcode 答案解析 golang解答
500195422331430LeetCode题解 - Java语言实现.zip
leetcode 答案LeetCode--哈希表 以上是我对“哈希表”问题的回答,都被leetcode的判断所接受。
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
http://blog.csdn.net/two_water/article/details/53004027 LeetCode_直方图最大面积(Largest Rectangle in Histogram)
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode 1 -200题所有源码 有问题私聊我