`
huntfor
  • 浏览: 201669 次
  • 性别: Icon_minigender_1
  • 来自: 杭州
社区版块
存档分类
最新评论

[leetcode]Largest Rectangle in Histogram

 
阅读更多

Largest Rectangle in Histogram

 

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.

这个算法是从网上看的,这里有详细的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。才使得有了这个形式不变式,是厉害。

 

总之这道题算法实在是太巧妙了!但是感觉这种算法完全是技巧型的,不容易归纳。

  • 大小: 10.6 KB
分享到:
评论

相关推荐

    LeetCode Largest Rectangle in Histogram

    在LeetCode这个著名的在线编程挑战平台上,有一道题目名为“Largest Rectangle in Histogram”(直译为“柱状图中的最大矩形”),这是一道与数据结构和算法密切相关的题目,旨在考察程序员对栈、动态规划以及几何...

    python-leetcode题解之084-Largest-Rectangle-in-Histogram

    python python_leetcode题解之084_Largest_Rectangle_in_Histogram

    c语言-leetcode题解之0084-largest-rectangle-in-histogram.zip

    c c语言_leetcode题解之0084_largest_rectangle_in_histogram.zip

    js-leetcode题解之84-largest-rectangle-in-histogram.js

    javascript js_leetcode题解之84-largest-rectangle-in-histogram.js

    LargestRectangleInHistogram

    http://blog.csdn.net/two_water/article/details/53004027 LeetCode_直方图最大面积(Largest Rectangle in Histogram)

    LeetCode C++全解

    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

    leetcode316-LeetCode:leetcode的解决方案

    Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:单调栈 Island Perimeter:简单对比(map+zip的使用) or 遍历查找 Max Area of Island:DFS(本来想用DP,发现出不来) Number of Islands:DFS My ...

    Leetcode题目+解析+思路+答案.pdf

    - **Largest Rectangle in Histogram**:在直方图中找到最大的矩形面积。 - **Maximal Rectangle**:在二维矩阵中找到最大的矩形。 - **Palindrome Number**:判断一个数字是否是回文数。 - **Search a 2D ...

    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/...

    LeetCodemaxarea-largest-rectangle-in-a-histogram:直方图中最大的矩形

    力扣最大面积直方图中最大的矩形 给定 n 个非负整数表示直方图的条形高度,其中每个条形的宽度为 1,求直方图中最大矩形的面积。 上面是一个直方图,其中每个条的宽度为 1,给定高度 = [2,1,5,6,2,3]。...

    LeetCode leetcode部分题解答代码实现

    * Largest Rectangle in Histogram:给定一个直方图,返回直方图中的最大矩形面积。这个题目需要使用栈的思想,将直方图中的每个矩形分解成更小的矩形,并找到最大矩形。 * Maximal Rectangle:给定一个矩形,返回...

    leetcode1-240题中文题解,md格式,java

    6. leetCode-84-Largest-Rectangle-in-Histogram.md:第84题,柱状图中最大的矩形,涉及到数组处理和栈的数据结构。 7. leetcode-130-Surrounded-Regions.md:第130题,包围的区域,可能涉及二维数组处理和深度优先...

    蓄水池算法leetcode-leetcode:leetcode

    largest-rectangle-in-histogram: 最长递增子序列: 最长公共自序列: Something about: best time to buy and sell stack: 单链表中的环,两个单链表的公共点。 populating-next-right-pointers-in-each-node-ii: ...

    leetcode卡-Array-LeetCode-Solution:数组-LeetCode-解决方案

    如"最宽的水平条"(Largest Rectangle in Histogram)。 5. **前缀和与后缀和**:通过计算数组的累积和,可以快速求解区间和问题。例如"连续子数组的最大和"(Maximum Subarray)。 6. **动态规划**:数组问题常与...

    LeetCode练习答案

    - **直方图中的最大矩形(Largest Rectangle in Histogram)**: 给定直方图的高度,计算能够组成的矩形的最大面积。 - **最大矩形(Maximal Rectangle)**: 在由'0'和'1'组成的二维矩阵中,找到只包含'1'的最大矩形,并...

    leetcode2-Misc-4:杂项4

    问题二:直方图中最大的矩形(Largest Rectangle in Histogram) 这是一个经典的几何问题,需要找到直方图(一种特殊形式的柱状图)中可以构成的最大矩形面积。解决这个问题通常采用栈作为辅助数据结构。遍历每个...

    股票买卖最佳时机leetcode-Java-Projects:Java项目和面试问题的存储库,用于编码面试的练习

    股票买卖最佳时机leetcode Java项目 这是 Java 项目的存储库。 它包含: 基于回溯的数独求解器。 许多编码面试问题的解决方案作为从InterviewBit 和Leetcode ...Largest_Rectangle_In_Histogram Least_C

    3、动态规划必练题(含解法).pdf

    11. **Largest Rectangle in Histogram** (柱状图中最大的矩形) 求柱状图中能构成的最大矩形面积。可以使用栈来辅助实现,维护当前高度和最大高度。 12. **Maximal Rectangle** (最大的矩形) 在一个01矩阵中找到...

Global site tag (gtag.js) - Google Analytics