Largest Rectangle in 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.
这个算法是从网上看的,这里有详细的debug步骤,可以帮助大家了解整个算法思想。
public int largestRectangleArea(int[] height) { if(height == null || height.length == 0){ return 0; } int[] copy = new int[height.length + 1]; copy = Arrays.copyOf(height, height.length + 1); Stack<Integer> stack = new Stack<Integer>(); int maxArea = 0; int i = 0; while(i < copy.length){ if(stack.isEmpty() || copy[stack.peek()] <= copy[i]){ stack.push(i++); }else{ int num = stack.pop(); maxArea = Math.max(maxArea,copy[num] * (stack.isEmpty() ? i : i - stack.peek() - 1)); } } return maxArea; }
程序中最让人费解的就是这两句:
if(stack.isEmpty() || copy[stack.peek()] <= copy[i])stack.push(i++);
1. stack为空可以理解,但是为什么copy[stack.peek()] <= copy[i]也要压栈呢?
还有这一句:
maxArea = Math.max(maxArea,copy[num] * (stack.isEmpty() ? i : i - stack.peek() - 1));
其实这一句debug的时候就可以理解了。
不过po主并没有解答这两个疑惑。这里我做一个简单的小结:
以为例。
首先来看第二个问题:已知栈中有[1,5,6]遇到了2,则将栈顶元素6弹出,计算出面积为6
【(i - stack.peek() - 1) * 6】然后根据条件还需要弹栈,第二次弹栈计算出面积为10。遇到1时发现不能达到弹栈要求。
这里是第一个问题:为什么1就不能继续弹了?
答:因为弹了也白弹:由[1,5,6]组成的面积一定会小于[1,5,6,2]组成的面积,因此这里对2选择压栈,只有这样,才有可能组成更大的矩型,不过原程序中的要求是copy[stack.peek()] <= copy[i]压栈,其实copy[stack.peek()] < copy[i]严格的小于也是可以的,不过是多做了一步多余的计算。
因此第一个问题copy[stack.peek()] <= copy[i]其实是由两个问题合并组成的:
第一次是对于递增的元素进行压栈,因为只有这样才可能使矩形面积越来越大;
第二次是弹栈,弹到1的时候,对2进行压栈,这样做类似于一种剪枝,因此没有必要继续弹了,当然选择继续弹栈也是完全可以的,不过都是多余的而已。
第二个问题只是简单的对于面积进行更新,不过代码中很巧妙的用了stack.isEmpty ? i : i - stack.peek() - 1因为copy数组开大了一个空间,即:数组最后有一个哨兵元素0。才使得有了这个形式不变式,是厉害。
总之这道题算法实在是太巧妙了!但是感觉这种算法完全是技巧型的,不容易归纳。
相关推荐
LeetCode题目Largest Rectangle in Histogram 解答
http://blog.csdn.net/two_water/article/details/53004027 LeetCode_直方图最大面积(Largest Rectangle in Histogram)
1. Introduction ... Largest Rectangle in Histogram ix. Maximal Rectangle x. Palindrome Number xi. Search a 2D Matrix xii. Search for a Range xiii. Search Insert Position xiv. Find Peak Element
Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:单调栈 Island Perimeter:简单对比(map+zip的使用) or 遍历查找 Max Area of Island:DFS(本来想用DP,发现出不来) Number of Islands:DFS My ...
leetcode 答案解析 golang解答
703.Kth_Largest_Element_in_a_Stream数据流中的第K大元素【LeetCode单题讲解系列】
421 | [Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) | [C++](./C++/maximum-xor-of-two-numbers-in-an-array.cpp) [Python](./Python/...
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
Leetcode Solutions in Rust, Advent of Code Solutions in Ru
力扣最大面积直方图中最大的矩形 给定 n 个非负整数表示直方图的条形高度,其中每个条形的宽度为 1,求直方图中最大矩形的面积。 上面是一个直方图,其中每个条的宽度为 1,给定高度 = [2,1,5,6,2,3]。...
algorithm templates and leetcode examples in Python3, you
leetcode 锈leetcode_in_rust 用 Rust 编写的 LeetCode 练习
LeetCode-Solutions-in-Swift.zip,swift 5中的leetcode解决方案
leetcode中文版
in Java 本项目是我对 上的问题的所有解答。LeetCode 是一个为准备 IT 面试的 OJ 平台,上面有非常丰富且高质量的问题。这里所有的解答都使用的 Java,并且你可以将本项目直接导入到 Eclipse 中。 每一道题都附带了 ...
vs code LeetCode 插件
大佬的leetcode刷题笔记(c++版本)
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
LeetCode 解决VS Code中的LeetCode问题 英文文件| 文件 :exclamation_mark: 注意 :exclamation_mark: ...快速开始产品特点登入/登出 只需在LeetCode Explorer单击“ Sign in to LeetCode , LeetCode Explorer使用LeetC