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; }
相关推荐
javascript js_leetcode题解之84-largest-rectangle-in-histogram.js
在LeetCode这个著名的在线编程挑战平台上,有一道题目名为“Largest Rectangle in Histogram”(直译为“柱状图中的最大矩形”),这是一道与数据结构和算法密切相关的题目,旨在考察程序员对栈、动态规划以及几何...
python python_leetcode题解之084_Largest_Rectangle_in_Histogram
c c语言_leetcode题解之0084_largest_rectangle_in_histogram.zip
6. leetCode-84-Largest-Rectangle-in-Histogram.md:第84题,柱状图中最大的矩形,涉及到数组处理和栈的数据结构。 7. leetcode-130-Surrounded-Regions.md:第130题,包围的区域,可能涉及二维数组处理和深度优先...
http://blog.csdn.net/two_water/article/details/53004027 LeetCode_直方图最大面积(Largest Rectangle in Histogram)
力扣最大面积直方图中最大的矩形 给定 n 个非负整数表示直方图的条形高度,其中每个条形的宽度为 1,求直方图中最大矩形的面积。 上面是一个直方图,其中每个条的宽度为 1,给定高度 = [2,1,5,6,2,3]。...
如"最宽的水平条"(Largest Rectangle in Histogram)。 5. **前缀和与后缀和**:通过计算数组的累积和,可以快速求解区间和问题。例如"连续子数组的最大和"(Maximum Subarray)。 6. **动态规划**:数组问题常与...
Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:单调栈 Island Perimeter:简单对比(map+zip的使用) or 遍历查找 Max Area of Island:DFS(本来想用DP,发现出不来) Number of Islands:DFS My ...
问题二:直方图中最大的矩形(Largest Rectangle in Histogram) 这是一个经典的几何问题,需要找到直方图(一种特殊形式的柱状图)中可以构成的最大矩形面积。解决这个问题通常采用栈作为辅助数据结构。遍历每个...
largest-rectangle-in-histogram: 最长递增子序列: 最长公共自序列: Something about: best time to buy and sell stack: 单链表中的环,两个单链表的公共点。 populating-next-right-pointers-in-each-node-ii: ...
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/...
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
股票买卖最佳时机leetcode Java项目 这是 Java 项目的存储库。 它包含: 基于回溯的数独求解器。 许多编码面试问题的解决方案作为从InterviewBit 和Leetcode ...Largest_Rectangle_In_Histogram Least_C
- **Largest Rectangle in Histogram**:在直方图中找到最大的矩形面积。 - **Maximal Rectangle**:在二维矩阵中找到最大的矩形。 - **Palindrome Number**:判断一个数字是否是回文数。 - **Search a 2D ...
* Largest Rectangle in Histogram:给定一个直方图,返回直方图中的最大矩形面积。这个题目需要使用栈的思想,将直方图中的每个矩形分解成更小的矩形,并找到最大矩形。 * Maximal Rectangle:给定一个矩形,返回...
- **直方图中的最大矩形(Largest Rectangle in Histogram)**: 给定直方图的高度,计算能够组成的矩形的最大面积。 - **最大矩形(Maximal Rectangle)**: 在由'0'和'1'组成的二维矩阵中,找到只包含'1'的最大矩形,并...
11. **Largest Rectangle in Histogram** (柱状图中最大的矩形) 求柱状图中能构成的最大矩形面积。可以使用栈来辅助实现,维护当前高度和最大高度。 12. **Maximal Rectangle** (最大的矩形) 在一个01矩阵中找到...