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

Question

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

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

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

O(n ^ 2)蛮力对我来说很清楚,我想要一个O(n log n)算法.我试图按照最大增加子序列O(n log n)算法的方式来思考动态编程,但我没有继续前进.我应该使用分而治之的算法吗？

PS:如果没有这样的解决方案,请求具有足够声誉的人删除分而治之标签.

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

Answer 1

上面的答案给出了代码中最好的O(n)解决方案,然而,他们的解释很难理解.使用堆栈的O(n)算法起初对我来说似乎很神奇,但是现在它对我来说都很有意义.好的,让我解释一下.

首先观察:

为了找到最大的矩形,若对所有的酒吧x,我们知道在其两侧的第一小酒吧,让我们说l和r,我们肯定height[x] * (r - l - 1)是我们可以利用巴的高度获得最佳的拍摄x.在下图中,1和2是5中的第一个中的第一个.

好的,我们假设我们可以在O(1)时间内为每个条形图执行此操作,然后我们可以在O(n)中解决此问题!通过扫描每个栏.

然后,问题出现了:对于每个栏,我们是否真的可以在O(1)时间内在其左侧和右侧找到第一个较小的栏？那似乎不可能吧？......通过使用增加的堆栈可以实现.

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

也许通过告诉你一个不断增加的堆栈可以完成这项工作并不令人信服,所以我将引导你完成这个.

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

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

然后你可以检查在增加的堆栈中(如下所示),因为stack[x],stack[x-1]它是左边第一个较小的,然后一个可以弹出的新元素stack[x]是右边第一个较小的元素.

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

我将通过矛盾来证明这一点.

首先,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)中的堆栈来求解直方图中的最大矩形.

恭喜!这真的是一个棘手的问题,我很高兴我的平淡无奇的解释并没有阻止你完成.附件是我证明的解决方案作为你的奖励:)

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 2

除了蛮力方法之外,还有三种方法可以解决这个问题.我会写下所有这些.java代码已通过名为leetcode的在线评判网站的测试:http://www.leetcode.com/onlinejudge#question_84.所以我相信代码是正确的.

解决方案1:动态编程+ n*n矩阵作为缓存

时间:O(n ^ 2),空间:O(n ^ 2)

基本思想:使用n*n矩阵dp [i] [j]缓存bar [i]和bar [j]之间的最小高度.从宽度为1的矩形开始填充矩阵.

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;
}

解决方案2:动态编程+ 2个数组作为缓存.

时间:O(n ^ 2),空间:O(n)

基本思路:这个解决方案就像解决方案1,但节省了一些空间.我们的想法是,在解决方案1中,我们构建了从第1行到第n行的矩阵.但是在每次迭代中,只有前一行有助于构建当前行.因此我们依次使用两个数组作为前一行和当前行.

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;
}

解决方案3:使用堆栈.

时间:O(n),空间:O(n)

该解决方案是棘手的,我学会了如何从做这个解释没有图形和解释与图表.我建议你在阅读下面的解释之前阅读这两个链接.没有图表很难解释,所以我的解释可能难以理解.

以下是我的解释:

1. 对于每个栏,我们必须能够找到包含此栏的最大矩形.所以这些n个矩形中最大的一个是我们想要的.

2. 要获得某个条形的最大矩形(比如bar [i],第(i + 1)条),我们只需找出包含该条形的最大间隔.我们所知道的是,这个区间中的所有条都必须至少与bar [i]相同.因此,如果我们计算出bar [i]左边有多少个连续的相同高度或更高的条形,并且在条形图右侧有多少个连续的相同高度或更高的条形图[ i],我们将知道间隔的长度,即bar [i]的最大矩形的宽度.

3. 要计算bar [i]左边的连续相同高度或更高的条形数,我们只需要找到左边最近的条形,它比条形[i]短,因为它们之间的所有条形这个条和条[i]将是连续的相同高度或更高的条形.

4. 我们使用堆栈动态地跟踪所有比某个条形更短的左边条.换句话说,如果我们从第一个栏迭代到bar [i],当我们到达bar [i]并且还没有更新堆栈时,堆栈应该存储所有不高于bar的栏[i] -1],包括bar [i-1]本身.我们将bar [i]的高度与堆栈中的每个条形进行比较,直到我们找到一个比bar [i]更短的条,这是最短的条形.如果bar [i]高于堆栈中的所有柱,则表示bar [i]左侧的所有柱都高于bar [i].

5. 我们可以在第i个栏的右侧做同样的事情.然后我们知道bar [i]区间有多少条.

   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 3

使用@ IVlad的答案 O(n)解决方案在Python中实现:

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

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

复制粘贴算法的描述(如果页面出现故障):

我们按从左到右的顺序处理元素,并保留一堆关于已开始但尚未完成的子图形的信息.每当新元素到达时,它都遵循以下规则.如果堆栈为空,我们通过将元素推入堆栈来打开一个新的子问题.否则,我们将它与堆栈顶部的元素进行比较.如果新的更大,我们再次推动它.如果新的相等,我们跳过它.在所有这些情况下,我们继续使用下一个新元素.如果新的较小,我们通过更新堆栈顶部元素的最大区域来完成最顶层的子问题.然后,我们丢弃顶部的元素,并重复保持当前新元素的过程.这样,所有子问题都完成,直到堆栈变空,或者其顶部元素小于或等于新元素,从而导致上述操作.如果所有元素都已处理,并且堆栈尚未清空,我们通过更新顶部元素的最大区域wrt来完成剩余的子问题.

对于元素的更新,我们找到包含该元素的最大矩形.观察除了跳过的那些元素之外的所有元素都执行了最大区域的更新.但是,如果跳过某个元素,则它与当时堆栈顶部的元素具有相同的最大矩形,稍后将更新.当然,最大矩形的高度是元素的值.在更新时,我们知道最大的矩形延伸到元素右侧的距离,因为这是第一次到达具有较小高度的新元素.如果我们将它存储在堆栈中,则可以获得最大矩形延伸到元素左侧的信息.

因此,我们修改了上述程序.如果立即推送新元素,或者因为堆栈为空或者它大于堆栈的顶部元素,则包含它的最大矩形向左延伸不比当前元素更远.如果在从堆栈中弹出多个元素后推送它,因为它小于这些元素,包含它的最大矩形向左延伸到最近弹出元素的那个.

每个元素最多被推送和弹出一次,并且在该过程的每个步骤中,至少推送或弹出一个元素.由于决策和更新的工作量是恒定的,因此算法的复杂性是通过摊销分析的O(n).

Answer 4

这里的其他答案在使用两个堆栈呈现O(n)-time,O(n)空间解决方案方面做得很好.关于这个问题的另一个观点是独立地为问题提供O(n)时间,O(n)空间解决方案,并且可以提供关于基于堆栈的解决方案工作原理的更多信息.

关键思想是使用称为笛卡尔树的数据结构.笛卡尔树是围绕输入数组构建的二叉树结构(尽管不是二叉搜索树).具体地,笛卡尔树的根构建在数组的最小元素之上,并且左子树和右子树是从子阵列递归地构造到最小值的左侧和右侧.

例如,这是一个示例数组及其笛卡尔树:

                 +----------------------- 23 ------+
                 |                                 |
  +------------- 26 --+                        +-- 79
  |                   |                        |
  31 --+              53 --+                   84
       |                   |
       41 --+              58 -------+
            |                        |
            59                  +-- 93
                                |
                                97

+----+----+----+----+----+----+----+----+----+----+----+
| 31 | 41 | 59 | 26 | 53 | 58 | 97 | 93 | 23 | 84 | 79 |
+----+----+----+----+----+----+----+----+----+----+----+

笛卡尔树在这个问题中有用的原因是手头的问题有一个非常好的递归结构.首先查看直方图中的最低矩形.最大矩形最终放置的位置有三个选项:

• 它可以直接通过直方图中的最小值.在这种情况下,为了使它尽可能大,我们想要使它像整个数组一样宽.

• 它可以完全在最小值的左侧.在这种情况下,我们递归地希望从子阵列形成的答案纯粹在最小值的左侧.

• 它可能完全属于最小值的权利.在这种情况下,我们递归地希望从子阵列形成的答案纯粹在最小值的右侧.

请注意,这个递归结构 - 找到最小值,对该值的左侧和右侧的子数组执行某些操作 - 完全匹配笛卡尔树的递归结构.实际上,如果我们在开始时可以为整个数组创建一个笛卡尔树,那么我们就可以通过从根向下递归地走向笛卡尔树来解决这个问题.在每个点,我们递归计算左右子阵列中的最佳矩形,以及通过在最小值下方拟合得到的矩形,然后返回我们找到的最佳选项.

在伪代码中,这看起来像这样:

function largestRectangleUnder(int low, int high, Node root) {
  /* Base case: If the range is empty, the biggest rectangle we
   * can fit is the empty rectangle.
   */
  if (low == high) return 0;

  /* Assume the Cartesian tree nodes are annotated with their
   * positions in the original array.
   */
  return max {
    (high - low) * root.value, // Widest rectangle under the minimum
    largestRectangleUnder(low,            root.index, root.left),
    largestRectnagleUnder(root.index + 1, high,       root.right)
  }
}

一旦我们有了笛卡尔树,这个算法花费时间O(n),因为我们只访问每个节点一次并且每个节点执行O(1)工作.

事实证明,有一种简单的线性时间算法可用于构建笛卡尔树.您可能认为构建一个的"自然"方式是扫描数组,找到最小值,然后从左右子阵列递归构建笛卡尔树.问题是找到最小值的过程非常昂贵,这可能需要时间Θ(n ²).

构建笛卡尔树的"快速"方法是从左到右扫描数组,一次添加一个元素.该算法基于以下关于笛卡尔树的观察:

• 首先,笛卡尔树遵循堆属性:每个元素都小于或等于其子元素.这样做的原因是,笛卡尔树的根是整个阵列中的最小值,其子女中最小的元素及其子阵等

• 其次,如果对笛卡尔树进行顺序遍历,则按照它们出现的顺序返回数组的元素.要知道为什么会这样,请注意,如果您对笛卡尔树进行顺序遍历,则首先访问最小值左侧的所有内容,然后访问最小值,然后访问最小值右侧的所有内容.这些访问以相同的方式递归地进行,因此最终将按顺序访问所有内容.

如果我们从数组的前k个元素的笛卡尔树开始并想要为第一个k + 1元素形成笛卡尔树,这两个规则给出了很多关于会发生什么的信息.这个新元素必须最终出现在笛卡尔树的右侧脊柱上 - 树的一部分是从根部开始形成的,只是向右移动 - 因为否则会在顺序遍历之后出现一些东西.并且,在正确的脊柱内,它必须以比它上面的所有东西更大的方式放置,因为我们需要遵守堆属性.

实际向笛卡尔树添加新节点的方法是从树中最右边的节点开始向上走,直到您点击树的根或找到值较小的节点.然后,您将新值作为其左子节点,将其作为最后一个节点.

这是一个小数组上的算法的痕迹:

+---+---+---+---+
| 2 | 4 | 3 | 1 |
+---+---+---+---+

2成为根.

  2 --+
      |  
      4

4大于2,我们不能向上移动.追加到右边.

+---+---+---+---+
| 2 | 4 | 3 | 1 |
+---+---+---+---+

  2 ------+
          |
      --- 3 
      |
      4

3小于4,越过它.不能超过2,因为它小于3.爬过4根的子树进入新值3的左边,3现在成为最右边的节点.

+---+---+---+---+
| 2 | 4 | 3 | 1 |
+---+---+---+---+

  +---------- 1
  |
  2 ------+
          |
      --- 3
      |
      4

1爬过根2,以2为根的整个树移动到1的左边,1现在是新的根 - 也是最右边的值.

+---+---+---+---+
| 2 | 4 | 3 | 1 |
+---+---+---+---+

虽然这可能似乎没有在线性时间内运行 - 你不会一次又一次地一直爬到树的根部吗？ - 你可以使用一个聪明的参数表明它在线性时间内运行.如果在插入过程中向上爬过右侧脊柱中的节点,则该节点最终会从右侧脊柱移开,因此在将来插入时无法重新扫描.因此,每个节点最多只扫描一次,因此完成的总工作是线性的.

现在是踢球者 - 你实际实现这种方法的标准方法是维护一堆与右脊柱上的节点相对应的值."走上去"和节点上的行为对应于从堆栈弹出节点.因此,构建笛卡尔树的代码如下所示:

Stack s;
for (each array element x) {
   pop s until it's empty or s.top > x
   push x onto the stack.
   do some sort of pointer rewiring based on what you just did.

这是一些实现这个想法的Java代码,由@Azeem提供!

import java.util.Stack;

public class CartesianTreeMakerUtil {

    private static class Node {
        int val;
        Node left;
        Node right;
    }

    public static Node cartesianTreeFor(int[] nums) {
        Node root = null;
        Stack<Node> s = new Stack<>();
        for(int curr : nums) {
            Node lastJumpedOver = null;
            while(!s.empty() && s.peek().val > curr) {
                lastJumpedOver = s.pop();
            }
            Node currNode = this.new Node();
            currNode.val = curr;
            if(s.isEmpty()) {
                root = currNode;
            }
            else {
                s.peek().right = currNode;
            }
            currNode.left = lastJumpedOver;
            s.push(currNode);
        }
        return root;
    }

    public static void printInOrder(Node root) {
        if(root == null) return;
        if(root.left != null ) {
            printInOrder(root.left);
        }
        System.out.println(root.val);
        if(root.right != null) {
            printInOrder(root.right);
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[args.length];
        for (int i = 0; i < args.length; i++) {
            nums[i] = Integer.parseInt(args[i]);
        }
        Node root = cartesianTreeFor(nums);
        tester.printInOrder(root);
    }
}

这里的堆栈操作可能看起来非常熟悉,因为这些是您在此处其他地方显示的答案中所做的精确堆栈操作.实际上,您可以考虑这些方法正在做什么,因为隐式构建笛卡尔树并在执行此过程中运行上面显示的递归算法.

我认为,了解笛卡尔树的优点在于它提供了一个非常好的概念框架,用于了解该算法为何能正常工作.如果你知道你正在做的是运行笛卡尔树的递归遍历,那么更容易看到你保证找到最大的矩形.另外,知道笛卡尔树的存在为您提供了解决其他问题的有用工具.笛卡尔树在快速数据结构的设计中出现,用于范围最小查询问题,并用于将后缀数组转换为后缀树.

Answer 5

O(N)中最简单的解决方案

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;
}