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
.
[balabala]
方法1: O(N^2) 处理高度数组中每个元素时,左右分别找到第一个比当前高度低的位置,分别记为left, right, 则right - left - 1就是当前高度能围成的最大矩形的宽度,据此算出面积并更新全局最大面积值。
方法2:O(N) 使用stack 保存到当前位置处的高度非递减索引值,遇到一个高度比栈顶位置低的位置 i 时暂停下来,说明 i 是stack 中那些高于位置i 的bar的右边界,正是时候停下来计算那些高度对应的矩形面积。因为stack中是非递减序列,pop直到栈顶位置的高度小于某个正在计算的高度,pop结束时的位置就是正在计算的bar 的左边界。实现有两个方式,方式1 (method2)计算每个位置到右边界围成的面积,遇到等值大数组的case会超时,方式2(method3)pop直到找出左边界时才停下来计算,在遇到等值大数组时可节约可观的计算量。
重做该题时写了method4,原意是想节省method2中的copy数组开辟的额外空间,但遇到等值大数组时超时,在eclipse中调试,打印两个for循环耗时,input是长度为300000值均为1的数组,各方法耗时情况如下:
方法 | 耗时 |
method2 | 74ms |
method3 | 28ms |
method4 | 46ms(30+ 16) |
method5 | 34ms(19 + 14) |
method6 | 24ms |
method5在method4基础上调整代码写法,去除一个多余的循环体,性能得到明显提升,让我大开眼界,不过仍然无法通过leetcode中的大case。另外通过比较method5和method3也可以看出构造一个for循环本身是有比较大的开销的。所以以后coding时要避免写不必要的循环体。比较method6 和method3, method6是以空间换时间,新开多一个元素的数组,最后一个元素是整个数组的最小值,以保证前面每个高度组成的矩形都得到计算,换句话说是替换外层循环体中的!stack.isEmpty()作用,节省了while循环和循环中if中的判断计算量。
[ref] http://www.cnblogs.com/lichen782/p/leetcode_Largest_Rectangle_in_Histogram.html
// method 1 public int largestRectangleArea(int[] height) { if (height == null) return 0; int n = height.length; int max = 0; for (int i = 0; i < n; i++) { int j = i - 1; while (j >= 0 && height[j] >= height[i]) { j--; } int left = i - j; j = i + 1; while (j < n && height[j] >= height[i]) { j++; } int right = j - i; max = Math.max(max, (left + right - 1) * height[i]); } return max; } // method 2 public int largestRectangleArea(int[] height) { LinkedList<Integer> stack = new LinkedList<Integer>(); int[] h = new int[height.length + 1]; h = Arrays.copyOf(height, h.length); int i = 0; int max = 0; while (i < h.length) { if (stack.isEmpty() || h[i] >= h[stack.peek()]) { stack.push(i++); } else { int currH = h[stack.pop()]; max = Math.max(max, currH * (stack.isEmpty() ? i : (i - stack.peek() - 1))); } } return max; } // method 3 public int largestRectangleArea(int[] height) { LinkedList<Integer> stack = new LinkedList<Integer>(); int max = 0; int i = 0; while(i < height.length || !stack.isEmpty()){ if(stack.isEmpty() || i < height.length && height[i] >= height[stack.peek()]){ stack.push(i++); }else{ int currH = height[stack.pop()]; while(!stack.isEmpty() && height[stack.peek()] == currH) stack.pop(); int left = stack.isEmpty() ? -1 : stack.peek(); max = Math.max(max, currH * (i - left - 1)); } } return max; } // method 4 public int largestRectangleArea4(int[] height) { if (height == null || height.length == 0) return 0; int max = 0; LinkedList<Integer> stack = new LinkedList<Integer>(); long start = System.currentTimeMillis(); for (int i = 0; i < height.length; i++) { if (stack.isEmpty() || height[i] >= height[stack.peek()]) { stack.push(i); } else { while (!stack.isEmpty() && height[i] <height[stack.peek()]) { int curr = stack.pop(); while (!stack.isEmpty() && height[curr] == height[stack.peek()]) { stack.pop(); } int width = stack.isEmpty() ? i : (i - stack.peek() - 1); max = Math.max(max, height[curr] * width); } stack.push(i); } } System.out.println("part1=" + (System.currentTimeMillis() - start)); start = System.currentTimeMillis(); int rightBound = height.length; while (!stack.isEmpty()) { int curr = stack.pop(); while (!stack.isEmpty() && height[curr] == height[stack.peek()]) { stack.pop(); } int width = stack.isEmpty() ? rightBound : (rightBound - stack.peek() - 1); max = Math.max(max, height[curr] * width); } System.out.println("part2=" + (System.currentTimeMillis() - start)); return max; } // method 5 public int largestRectangleArea5(int[] height) { if (height == null || height.length == 0) return 0; int max = 0; LinkedList<Integer> stack = new LinkedList<Integer>(); long start = System.currentTimeMillis(); int i = 0; while(i < height.length) { if (stack.isEmpty() || height[i] >= height[stack.peek()]) { stack.push(i++); } else { int curr = stack.pop(); while (!stack.isEmpty() && height[curr] == height[stack.peek()]) { stack.pop(); } int width = stack.isEmpty() ? i : (i - stack.peek() - 1); max = Math.max(max, height[curr] * width); } } System.out.println("part1=" + (System.currentTimeMillis() - start)); start = System.currentTimeMillis(); int rightBound = height.length; while (!stack.isEmpty()) { int curr = stack.pop(); while (!stack.isEmpty() && height[curr] == height[stack.peek()]) { stack.pop(); } int width = stack.isEmpty() ? rightBound : (rightBound - stack.peek() - 1); max = Math.max(max, height[curr] * width); } System.out.println("part2=" + (System.currentTimeMillis() - start)); return max; } // method 6 public int largestRectangleArea6(int[] h) { if (h == null || h.length == 0) return 0; int max = 0; int[] height = new int[h.length + 1]; for (int i = 0; i < h.length; i++) { height[i] = h[i]; } LinkedList<Integer> stack = new LinkedList<Integer>(); for (int i = 0; i < height.length; i++) { if (stack.isEmpty() || height[i] >= height[stack.peek()]) { stack.push(i); } else { while (!stack.isEmpty() && height[i] <height[stack.peek()]) { int curr = stack.pop(); while (!stack.isEmpty() && height[curr] == height[stack.peek()]) { stack.pop(); } int width = stack.isEmpty() ? i : (i - stack.peek() - 1); max = Math.max(max, height[curr] * width); } stack.push(i); } } return max; }
相关推荐
LeetCode题目Largest Rectangle in Histogram 解答
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
LeetCode-Solutions-in-Swift.zip,swift 5中的leetcode解决方案
IDEA 插件,lettcode刷题,leetcode-editor7.4版本下载进行本地导入(直接将压缩包拖进IDEA即可)
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
leetcode 答案解析 golang解答
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
leetcode-helper-1.7.1
leetcode-tag-dynamic programming
然后进入到LeetCode-Spider目录中修改config.json,其中outputDir需要填写该工程的/docs/views文件夹路径 { "username": "aaa", "password": "bbb", "outputDir": "/Users/liuyao/Downloads/LeetCode-Blog-Test/docs...
leetcode-cli 注意:这个存储库是为了临时使用而分叉的。 注意:从 webbrowser 复制 cookie 并使用leetcode user -c可以临时修复不能。 一个享受 leetcode 的高效 cli 工具! 非常感谢 leetcode.com,一个非常棒的...
leetcode-tag-Tree
leetcode-tag-Stack