首页 文章

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

提问于
浏览 次
53

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

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

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

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

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

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

algorithm

11 回答

  • 15

    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;
}
    回复于
  • 1

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

    A）对于每个索引，找到直方图内最大的矩形，该矩形结束于该索引处，其中索引列接触矩形的顶部并记住矩形开始的位置 . 这可以使用基于堆栈的算法在O（n）中完成 .

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

    C）对于每个索引，组合（A）和（B）的结果以确定该索引处的列接触矩形顶部的最大矩形 . O（n）如（A） .

    D）由于最大矩形必须被直方图的某一列触及，因此最大的矩形是步骤（C）中找到的最大矩形 .

    困难的部分是实施（A）和（B），我认为这是JF塞巴斯蒂安可能解决的问题，而不是所述的一般问题 .

    回复于
  • 1

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

    解决方案1： dynamic programming + n*n matrix as cache

    时间：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： dynamic programming + 2 arrays as cache .

    时间：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： use stack .

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

    这个解决方案很棘手，我从explanation without graphs和explanation with graphs学到了如何做到这一点 . 我建议你在阅读下面的解释之前阅读这两个链接 . 没有图表很难解释，所以我的解释可能很难理解 .

    以下是我的解释：

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

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

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

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

    • 我们可以在第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;
}
    回复于
  • 1

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

    First observation:

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

    好吧，我们假设我们可以在每个柱的O（1）时间内完成此操作，然后我们可以在O（n）中解决这个问题！通过扫描每个栏 .

    enter image description here

    然后，问题出现了：对于每个柱子，我们能否在O（1）时间内在左侧和右侧找到第一个较小的小条？那似乎不可能吧？ ......通过使用增加的堆栈可以实现 .

    Why using an increasing stack can keep track of the first smaller on its left and right?

    也许通过告诉你越来越多的堆栈可以完成这项工作并不令人信服，所以我将引导你完成这个任务 .

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

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

    然后你可以检查在增加的堆栈中（如下所示），对于 stack[x] ， stack[x-1] 是它左边的第一个较小的，然后一个可以弹出 stack[x] out的新元素是右边第一个较小的元素 .

    enter image description here

    Still can't believe stack[x-1] is the first smaller on the left on stack[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]必须是第一个较小的 .

    Summary:

    增加堆栈可以跟踪每个元素左右的第一个较小的元素 . 通过使用此属性，可以通过使用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
    回复于
  • 5

    在Python中实现the @IVlad's answer O（n）解决方案：

    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

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

    复制粘贴算法的描述（如果页面出现故障）：

    我们按从左到右的顺序处理元素，并保留一堆关于已开始但尚未完成的子图表的信息 . 每当新元素到达时，它都遵守以下规则 . 如果堆栈为空，我们通过将元素推入堆栈来打开一个新的子问题 . 否则，我们将它与堆栈顶部的元素进行比较 . 如果新的更大，我们再次推动它 . 如果新的相等，我们跳过它 . 在所有这些情况下，我们继续使用下一个新元素 . 如果新的较小，我们通过更新最大区域w.r.t来完成最顶层的子问题 . 堆栈顶部的元素 . 然后，我们丢弃顶部的元素，并重复保持当前新元素的过程 . 这样，所有子问题都完成，直到堆栈变空，或者其顶部元素小于或等于新元素，从而导致上述操作 . 如果所有元素都已处理，并且堆栈尚未清空，我们通过更新w.r.t的最大区域来完成剩余的子问题 . 到顶部的元素 . 对于更新w.r.t.一个元素，我们找到包含该元素的最大矩形 . 观察除了跳过的那些元素之外的所有元素都执行了最大区域的更新 . 但是，如果跳过一个元素，它与当时堆栈顶部的元素具有相同的最大矩形，稍后将更新 . 当然，最大矩形的高度是元素的值 . 在更新时，我们知道最大的矩形延伸到元素右侧的距离，因为这是第一次到达具有较小高度的新元素 . 如果我们将它存储在堆栈中，则可以获得最大矩形延伸到元素左侧的信息 . 因此，我们修改了上述程序 . 如果立即推送新元素，或者因为堆栈为空或者它大于堆栈的顶部元素，则包含它的最大矩形向左延伸不比当前元素更远 . 如果在从堆栈中弹出多个元素后推送它，因为它小于这些元素，包含它的最大矩形向左延伸到最近弹出元素的那个 . 每个元素最多被推送和弹出一次，并且在该过程的每个步骤中，至少推送或弹出一个元素 . 由于决策和更新的工作量是恒定的，因此算法的复杂性是通过摊销分析的O（n） .

    回复于
  • 54

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

    关键的想法是使用一个名为Cartesian tree的数据结构 . 笛卡尔树是围绕输入数组构建的二叉树结构（尽管不是二叉搜索树） . 具体来说，笛卡尔树的根 Build 在最小元素之上对于数组，左子树和右子树是从最小值左侧和右侧的子阵列递归构造的 .

    例如，这是一个示例数组及其笛卡尔树：

    +----------------------- 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）工作 .

    事实证明，'s a simple, linear-time algorithm for building Cartesian trees. The 386776 way you'd可能认为构建一个将扫描整个数组，找到最小值，然后从左右子阵列递归构建一个笛卡尔树 . 问题是找到最小值的过程非常昂贵，这可能需要时间Θ（n2） .

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

    • 首先，笛卡尔树遵循堆属性：每个元素都小于或等于其子元素 . 这样做的原因是笛卡尔树根是整个数组中最小的值，它的子元素是子数组中最小的元素，等等 .

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

    如果我们从数组的前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);
    }
}

    这里的堆栈操作可能看起来非常熟悉，那是因为 these are the exact stack operations that you would do in the answers shown elsewhere here. 事实上，您可以想到这些方法正在做什么，因为 implicitly 构建了笛卡尔树并在执行此过程中运行上面显示的递归算法 .

    我认为，了解笛卡尔树的优点在于它提供了一个非常好的概念框架，用于了解该算法为何正常工作 . 如果你知道你更容易看到你保证找到最大的矩形 . 另外，知道笛卡尔树的存在为您提供了解决其他问题的有用工具 . 笛卡尔树出现在range minimum query problem的快速数据结构设计中，用于将suffix arrays转换为suffix trees .

    回复于
  • 2

    我编写了这个编码，在某种意义上感觉更好：

    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)
    回复于
  • 6

    您可以使用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:i-s.top()-1);
        if(area >maxArea)
            maxArea= area;
    }
  }
  while(!s.empty()){
    int top = s.top();s.pop();
    area= histo[top]* (s.empty()?i:i-s.top()-1);
    if(area >maxArea)
        maxArea= area;
 }
 return maxArea;
}

    有关解释，请阅读http://www.geeksforgeeks.org/largest-rectangle-under-histogram/

    回复于
  • -1

    堆栈解决方案是迄今为止我见过的最聪明的解决方案之一 . 而且可能有点难以理解为什么会起作用 .

    我已经采取了一些措施来详细解释here .

    帖子摘要点： -

    • 我们的大脑认为的一般方式是： -

    • 创建每种情况并尝试找到解决问题所需的约束的值 .

    • 我们很乐意将其转换为代码为： - 为每种情况找到约束（min）的值（对（i，j））

    聪明的解决方案试图解决问题 . 对于tha区域的每个约束/最小值，左右极值的最佳可能性是什么？

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

    • 小思想说，第一个最左边的值小于 current min ，同样第一个最右边的值小于当前最小值 .

    • 所以现在我们需要看看我们是否能找到一种聪明的方法来找到小于当前值的第一个左右值 .

    • 要想：如果我们遍历数组部分说到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是最大值 . （这里感兴趣的值是可能对后面的数组感兴趣的值）

    • 因为，我们从左到右，每个最小值/当前值 - 我们不知道数组的右侧是否有一个小于它的元素 .

    • 所以我们必须将它保留在内存中，直到我们知道这个值是无用的 . （因为找到了一个较小的值）

    • 这一切都导致了我们自己的 stack 结构的使用 .

    • 我们继续堆叠，直到我们不知道它无用 .

    • 一旦我们知道事情是废话，我们从堆栈中删除 .

    • 因此，对于每个最小值，要找到其左侧较小的值，我们执行以下操作： -

    • 弹出更大的元素（无用的值）

    • 小于值的第一个元素是左极端 . 我到我们的分钟 .

    • 我们可以从数组的右侧做同样的事情，我们将得到j到我们的分钟 .

    它's quite hard to explain this, but if this is making sense then I'建议阅读完整的文章here，因为它有更多的见解和细节 .

    回复于
  • 2

    我要感谢@templatetypedef他/她非常详细和直观的答案 . 下面的Java代码基于他建议使用笛卡尔树并解决O（N）时间和O（N）空间中的问题 . 我建议您在阅读下面的代码之前阅读@ templatetypedef的答案 . 代码以leetcode的问题解决方案的格式给出：https://leetcode.com/problems/largest-rectangle-in-histogram/description/并传递所有96个测试用例 .

    class Solution {

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

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

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

    if (low == high) {
        if(0 <= low && low <= nums.length - 1) {
            return nums[low];
        }
        return 0;
    }

    /* Assume the Cartesian tree nodes are annotated with their
     * positions in the original array.
     */
    int leftArea = -1 , rightArea= -1;
    if(root.left != null) {
        leftArea = largestRectangleUnder(low, root.index - 1 , root.left, nums);
    }
    if(root.right != null) {
        rightArea = largestRectangleUnder(root.index + 1, high,root.right, nums);
    }
    return Math.max((high - low  + 1) * root.val, 
           Math.max(leftArea, rightArea));
}

public int largestRectangleArea(int[] heights) {
    if(heights == null || heights.length == 0 ) {
        return 0;
    }
    if(heights.length == 1) {
        return heights[0];
    }
    Node root = getCartesianTreeFromArray(heights);
    return largestRectangleUnder(0, heights.length - 1, root, heights);
}

    }

    回复于
  • 42

    使用Divide and Conquer还有另一种解决方案 . 它的算法是：

    1）将阵列分成2个部分，最小高度作为断点

    2）最大面积是最大值：a）阵列的最小高度*大小b）左半数组中的最大矩形c）右半数组中的最大矩形

    时间复杂度来自O（nlogn）

    回复于

相关问题