最大化直方图下的矩形区域

我有一个整数高度和恒定宽度的直方图1.我想要最大化直方图下的矩形区域。 例如：

_ | | | |_ | | | |_ | | 

答案是6,3 * 2，使用col1和col2。

O（n ^ 2）蛮力对我来说很清楚，我想要一个O（n log n）algorithm。 我试图按照最大递增子序列O（n log n）algorithm来思考dynamic编程，但是我不会前进。 我应该使用分而治之algorithm吗？

PS：如果没有这样的解决scheme，要求有足够信誉的人去除分而治之的标签。

在mho的评论之后：我的意思是最大的矩形区域完全适合。 （感谢j_random_hacker澄清:)）。

Answer 1

除了powershell方法之外，还有三种方法可以解决这个问题。 我会写下所有的。 java代码已通过在线评审站点的testing，名为leetcode： http ： //www.leetcode.com/onlinejudge#question_84 。 所以我确信代码是正确的。

解决scheme1： dynamic编程+ n * nmatrix作为caching

时间：O（n ^ 2），空间：O（n ^ 2）

基本思路：用n * nmatrixdp [i] [j]cachingbar [i]和bar [j]之间的最小高度。 从宽度为1的矩形开始填充matrix。

 public int solution1(int[] height) { int n = height.length; if(n == 0) return 0; int[][] dp = new int[n][n]; int max = Integer.MIN_VALUE; for(int width = 1; width <= n; width++){ for(int l = 0; l+width-1 < n; l++){ int r = l + width - 1; if(width == 1){ dp[l][l] = height[l]; max = Math.max(max, dp[l][l]); } else { dp[l][r] = Math.min(dp[l][r-1], height[r]); max = Math.max(max, dp[l][r] * width); } } } return max; } 

解决scheme2： dynamic编程+ 2个数组作为caching 。

时间：O（n ^ 2），空间：O（n）

基本思路：这个解决scheme就像解决scheme1，但是节省了一些空间。 我们的想法是，在解决scheme1中，我们构build了从第1行到第n行的matrix。 但是在每一次迭代中，只有前一行有助于构build当前行。 所以我们使用两个数组作为前一行和当前行轮stream。

 public int Solution2(int[] height) { int n = height.length; if(n == 0) return 0; int max = Integer.MIN_VALUE; // dp[0] and dp[1] take turns to be the "previous" line. int[][] dp = new int[2][n]; for(int width = 1; width <= n; width++){ for(int l = 0; l+width-1 < n; l++){ if(width == 1){ dp[width%2][l] = height[l]; } else { dp[width%2][l] = Math.min(dp[1-width%2][l], height[l+width-1]); } max = Math.max(max, dp[width%2][l] * width); } } return max; } 

解决scheme3： 使用堆栈 。

时间：O（n），空间：O（n）

这个解决scheme是棘手的，我学会了如何做到这一点， 没有graphics和解释与图解释 。 我build议你在阅读下面的解释之前阅读这两个链接。 没有图表很难解释，所以我的解释可能很难遵循。

以下是我的解释：

1. 对于每个酒吧，我们必须能够find包含这个酒吧的最大的矩形。 所以这n个矩形中最大的一个是我们想要的。

2. 为了得到某个酒吧的最大长方形（比如bar [i]，第（i + 1）酒吧），我们只需要找出包含这个酒吧的最大间隔。 我们所知道的是，这个间隔中的所有酒吧必须至less与bar [i]一样的高度。 因此，如果我们计算bar [i]的左侧有多less连续的同高或更高的钢筋，并且在钢筋的右侧有多less个连续的同高或更高的钢筋[ i]，我们将知道间隔的长度，这是bar [i]最大矩形的宽度。

3. 要计算bar [i]左侧连续相同高度或更高的小节的数量，我们只需要find左边比bar [i]短的最近的小节，因为所有小节这个酒吧和酒吧[i]将连续相同的高度或更高的酒吧。

4. 我们使用一个堆栈来dynamic地跟踪所有比某个栏更短的左栏。 换句话说，如果我们从第一个条到第[i]条迭代，当我们到达条[i]并且没有更新堆时，堆栈应该存储所有不高于bar的条[i -1]，包括bar [i-1]本身。 我们比较酒吧[我]的高度与每个酒吧在堆栈中，直到我们发现一个比酒吧[我]，这是最短的酒吧。 如果栏[i]高于堆栈中的所有栏，则表示栏[i]左侧的所有栏都高于栏[i]。

5. 我们可以在第i个栏的右侧做同样的事情。 那么我们知道吧[我]有多less酒吧在那里的时间间隔。

    public int solution3(int[] height) { int n = height.length; if(n == 0) return 0; Stack<Integer> left = new Stack<Integer>(); Stack<Integer> right = new Stack<Integer>(); int[] width = new int[n];// widths of intervals. Arrays.fill(width, 1);// all intervals should at least be 1 unit wide. for(int i = 0; i < n; i++){ // count # of consecutive higher bars on the left of the (i+1)th bar while(!left.isEmpty() && height[i] <= height[left.peek()]){ // while there are bars stored in the stack, we check the bar on the top of the stack. left.pop(); } if(left.isEmpty()){ // all elements on the left are larger than height[i]. width[i] += i; } else { // bar[left.peek()] is the closest shorter bar. width[i] += i - left.peek() - 1; } left.push(i); } for (int i = n-1; i >=0; i--) { while(!right.isEmpty() && height[i] <= height[right.peek()]){ right.pop(); } if(right.isEmpty()){ // all elements to the right are larger than height[i] width[i] += n - 1 - i; } else { width[i] += right.peek() - i - 1; } right.push(i); } int max = Integer.MIN_VALUE; for(int i = 0; i < n; i++){ // find the maximum value of all rectangle areas. max = Math.max(max, width[i] * height[i]); } return max; } 

Answer 2

上面的答案已经给出了最好的O（n）代码解决scheme，但是，他们的解释很难理解。 起初，使用堆栈的O（n）algorithm对我来说似乎很神奇，但是现在对我来说这一切都是有意义的。 好的，让我解释一下。

首先观察：

要find最大的矩形，如果对于每一个条x ，我们知道它的每一边的第一个较小的条，我们说l和r ，我们确定height[x] * (r - l - 1)可以通过使用栏x高度得到。 在下图中，1和2是第一个较小的5。

好吧，我们假设我们可以在O（1）的时间内为每个柱做到这一点，那么我们可以在O（n）中解决这个问题！ 通过扫描每个栏。

那么问题就出现了：对于每一个酒吧，我们真的能够在O（1）时间的左边和右边find第一个小酒吧吗？ 这似乎不可能的权利？ …有可能通过使用增加的堆栈。

为什么使用增加的堆栈可以跟踪其左右两侧的第一个较小的堆栈？

也许通过告诉你，一个越来越多的工作可以完成这个工作根本就没有说服力，所以我会带你走过去。

首先，为了保持堆栈增加，我们需要一个操作：

 while x < stack.top(): stack.pop() stack.push(x) 

然后你可以检查在增加的堆栈中（如下图所示），对于stack[x] ， stack[x-1]是左边第一个较小的，那么一个可以popupstack[x]的新元素是第一个较小的权利。

还是不敢相信栈[x-1]是堆栈[x]左边第一个较小的？

我将通过矛盾来certificate这一点。

首先， stack[x-1] < stack[x]是肯定的。 但是让我们假设stack[x-1]不是stack[x]左边的第一个较小的。

那么第一个较小的fs哪里呢？

 If fs < stack[x-1]: stack[x-1] will be popped out by fs, else fs >= stack[x-1]: fs shall be pushed into stack, Either case will result fs lie between stack[x-1] and stack[x], which is contradicting to the fact that there is no item between stack[x-1] and stack[x]. 

所以栈[x-1]必须是第一个较小的。

概要：

增加堆栈可以跟踪每个元素的左右第一个较小的值。 通过使用这个属性，直方图中的最大矩形可以通过使用O（n）中的堆栈来解决。

恭喜！ 这真是一个棘手的问题，我很高兴我的平淡的解释并没有阻止你完成。 附上是我的certificate解决scheme作为你的奖励:)

 def largestRectangleArea(A): ans = 0 A = [-1] + A A.append(-1) n = len(A) stack = [0] # store index for i in range(n): while A[i] < A[stack[-1]]: h = A[stack.pop()] area = h*(i-stack[-1]-1) ans = max(ans, area) stack.append(i) return ans 

Answer 3

在@IVlad的答案 Python的实现O（n）解决scheme：

 from collections import namedtuple Info = namedtuple('Info', 'start height') def max_rectangle_area(histogram): """Find the area of the largest rectangle that fits entirely under the histogram. """ stack = [] top = lambda: stack[-1] max_area = 0 pos = 0 # current position in the histogram for pos, height in enumerate(histogram): start = pos # position where rectangle starts while True: if not stack or height > top().height: stack.append(Info(start, height)) # push elif stack and height < top().height: max_area = max(max_area, top().height*(pos-top().start)) start, _ = stack.pop() continue break # height == top().height goes here pos += 1 for start, height in stack: max_area = max(max_area, height*(pos-start)) return max_area 

例：

 >>> f = max_rectangle_area >>> f([5,3,1]) 6 >>> f([1,3,5]) 6 >>> f([3,1,5]) 5 >>> f([4,8,3,2,0]) 9 >>> f([4,8,3,1,1,0]) 9 

使用一堆不完整的子问题进行线性search

复制粘贴algorithm的描述（如果页面停止）：

我们按照从左到右的顺序处理元素，并保存一堆有关已启动但尚未完成子图的信息。 每当一个新元素到达时，它将受到以下规则的约束。 如果堆栈是空的，我们通过将元素推入堆栈来打开一个新的子问题。 否则，我们将它与堆栈顶部的元素进行比较。 如果新的更大，我们再次推它。 如果新的平等，我们跳过它。 在所有这些情况下，我们继续下一个新的元素。 如果新的更less，我们通过更新堆栈顶部的元素的最大面积来完成最上面的子问题。 然后，我们丢弃顶部的元素，并重复该过程，保持当前的新元素。 这样，所有的子问题都会被完成，直到堆栈变空或者其顶层元素小于或等于新元素，从而导致上述操作。 如果所有的元素都被处理了，堆栈还没有被清空，我们通过更新最上面的元素来完成剩下的子问题。

对于元素的更新，我们find包含该元素的最大的矩形。 注意除了那些被跳过的元素外，对所有元素都进行了最大区域的更新。 然而，如果一个元素被跳过，它将具有与当时堆栈顶部的元素相同的最大矩形，这个元素将在稍后被更新。 最大的矩形的高度当然是元素的值。 在更新的时候，我们知道最大的矩形在元素的右边有多远，因为这是第一次到达了一个更小的新元素。 如果我们将它存储在堆栈中，那么最大矩形在元素左边延伸的距离也是可用的。

因此，我们修改上述程序。 如果立即推送一个新的元素，或者因为堆栈是空的或者它大于堆栈的顶层元素，那么包含它的最大矩形向左延伸，不会比当前元素更远。 如果在popup多个元素之后按下它，因为它小于这些元素，则包含它的最大的矩形向左延伸到最近popup的元素。

每个元素最多被顶推一次，并且在过程的每一步中至less有一个元素被推或者popup。 由于决策和更新的工作量是不变的，algorithm的复杂度是O（n），通过摊销分析。

Answer 4

O（N）中最简单的解决scheme

 long long getMaxArea(long long hist[], long long n) { stack<long long> s; long long max_area = 0; long long tp; long long area_with_top; long long i = 0; while (i < n) { if (s.empty() || hist[s.top()] <= hist[i]) s.push(i++); else { tp = s.top(); // store the top index s.pop(); // pop the top area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1); if (max_area < area_with_top) { max_area = area_with_top; } } } while (!s.empty()) { tp = s.top(); s.pop(); area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1); if (max_area < area_with_top) max_area = area_with_top; } return max_area; } 

Answer 5

还有另一个使用分而治之的解决scheme。 algorithm是：

1）将arrays分成两部分，以最小高度作为断点

2）最大面积是以下最大值：a）arrays的最小高度*尺寸b）左半arrays中的最大矩形c）右半arrays中的最大矩形

时间复杂度达到O（nlogn）

Answer 6

我不明白其他条目，但我想我知道如何在O（n）中做到这一点如下。

A）对于每个索引，find直方图内最大的矩形，该索引结束于该索引处，索引列触及矩形的顶部，并记住矩形的起始位置。 这可以使用基于堆栈的algorithm在O（n）中完成。

B）类似地，对于每个索引，find从该索引开始的最大的矩形，其中索引列接触矩形的顶部，并记住矩形的结束位置。 另外O（n）使用与（A）相同的方法，但向后扫描直方图。

C）对于每个索引，合并（A）和（B）的结果以确定该索引处的列触及矩形顶部的最大矩形。 O（n）像（A）一样。

D）由于最大的矩形必须被直方图的某一列所触及，所以最大的矩形是步骤（C）中find的最大的矩形。

最困难的部分是实施（A）和（B），我认为这是JF Sebastian可能解决的问题，而不是所说的一般问题。

Answer 7

堆栈解决scheme是迄今为止我见过的最聪明的解决scheme之一。 这可能有点难以理解为什么这个工作。

我在这里详细解释了这个问题 。

文章摘要：

• 我们大脑认为的一般方法是：
  • 创造每一种情况，试图找出解决问题所需要的限制的价值。
  • 我们高兴地将其转换为以下代码： – 为每个情况（pair（i，j））查找contraint（min）的值

聪明的解决scheme试图翻转这个问题。 对于每个区域的constraint/min ，什么是最好的左右极值？

• 所以如果我们遍历数组中的每个可能的min 。 每个值的左右极值是多less？

  • 小思想说，第一个最左边的值小于current min ，类似地，第一个最右边的值小于当前的分钟。

• 所以现在我们需要看看能否find一个聪明的方法来find比当前值更小的第一个左值和右值。

• 想一想 ：如果我们已经遍历数组，直到min_i，那么如何构造min_i + 1的解？

• 我们需要在左边第一个小于min_i的值。

• 反转声明：我们需要忽略min_i左侧的大于min_i的所有值。 当我们发现第一个小于min_i（i）的值时停止。 一旦我们越过它，曲线上的低谷就变得无用了 。 在直方图中，（2 4 3）=>如果3是min_i，则4较大是不感兴趣的。
• Corrollary ：在一个范围（i，j）。 j是我们正在考虑的最小值。j和其左边的值i之间的所有值都是无用的。 即使进一步计算。
• 右侧任何直方图的最小值大于j，将被绑定在j。 左边的兴趣值形成一个单调递增的序列，其中j是最大的值。 （这里感兴趣的值是后面的数组可能感兴趣的可能值）
• 因为，我们从左到右，对于每个最小值/当前值 – 我们不知道数组的右侧是否会有一个小于它的元素。
  • 所以我们必须记住它，直到我们知道这个值是无用的。 （因为find一个更小的值）

• 所有这些都导致了我们自己的stack结构的使用。

  • 我们继续堆栈，直到我们不知道它是无用的。
  • 一旦我们知道事情是废话，我们从堆栈中删除。

• 因此，对于每个最小值find它的左侧较小的值，我们做以下事情： –

  1. popup更大的元素（无用的值）
  2. 小于该值的第一个元素是左边极限。 我到我们分钟。
• 我们可以从数组的右侧做同样的事情，我们将得到我们的最小。

这是很难解释，但如果这是有道理的，那么我build议阅读完整的文章，因为它有更多的见解和细节。

Answer 8

我编码这个，感觉好一点：

 import java.util.Stack; class StackItem{ public int sup; public int height; public int sub; public StackItem(int a, int b, int c){ sup = a; height = b; sub =c; } public int getArea(){ return (sup - sub)* height; } @Override public String toString(){ return " from:"+sup+ " to:"+sub+ " height:"+height+ " Area ="+getArea(); } } public class MaxRectangleInHistogram { Stack<StackItem> S; StackItem curr; StackItem maxRectangle; public StackItem getMaxRectangleInHistogram(int A[], int n){ int i = 0; S = new Stack(); S.push(new StackItem(0,0,-1)); maxRectangle = new StackItem(0,0,-1); while(i<n){ curr = new StackItem(i,A[i],i); if(curr.height > S.peek().height){ S.push(curr); }else if(curr.height == S.peek().height){ S.peek().sup = i+1; }else if(curr.height < S.peek().height){ while((S.size()>1) && (curr.height<=S.peek().height)){ curr.sub = S.peek().sub; S.peek().sup = i; decideMaxRectangle(S.peek()); S.pop(); } S.push(curr); } i++; } while(S.size()>1){ S.peek().sup = i; decideMaxRectangle(S.peek()); S.pop(); } return maxRectangle; } private void decideMaxRectangle(StackItem s){ if(s.getArea() > maxRectangle.getArea() ) maxRectangle = s; } } 

只需注意：

 Time Complexity: T(n) < O(2n) ~ O(n) Space Complexity S(n) < O(n) 

Answer 9

您可以使用O（n）方法使用堆栈来计算直方图下的最大面积。

 long long histogramArea(vector<int> &histo){ stack<int> s; long long maxArea=0; long long area= 0; int i =0; for (i = 0; i < histo.size();) { if(s.empty() || histo[s.top()] <= histo[i]){ s.push(i++); } else{ int top = s.top(); s.pop(); area= histo[top]* (s.empty()?i:is.top()-1); if(area >maxArea) maxArea= area; } } while(!s.empty()){ int top = s.top();s.pop(); area= histo[top]* (s.empty()?i:is.top()-1); if(area >maxArea) maxArea= area; } return maxArea; } 

为了解释你可以在这里阅读http://www.geeksforgeeks.org/largest-rectangle-under-histogram/