85.Maximal-Rectangle

85. Maximal Rectangle

题目地址

https://leetcode.com/problems/maximal-rectangle/

题目描述

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Example:
Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

代码

Approach #1 Brute Force

Trivially we can enumerate every possible rectangle. This is done by iterating over all possible combinations of coordinates (x1, y1) and (x2, y2) and letting them define a rectangle with the coordinates being opposite corners. This is too slow to pass all test cases.

Time: O(N^3) Space: O(1)

 public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxarea = 0;
        for (int i = 0; i < heights.length; i++) {
            for (int j = i; j < heights.length; j++) {
                int minheight = Integer.MAX_VALUE;
                for (int k = i; k <= j; k++)
                    minheight = Math.min(minheight, heights[k]);
                maxarea = Math.max(maxarea, minheight * (j - i + 1));
            }
        }
        return maxarea;
    }
}

Better Brote force

Time: O(N^2) Space: O(1)

 public class Solution {
    public int largestRectangleArea(int[] heights) {
        int maxarea = 0;
        for (int i = 0; i < heights.length; i++) {
            int minheight = Integer.MAX_VALUE;
            for (int j = i; j < heights.length; j++) {
                minheight = Math.min(minheight, heights[j]);
                maxarea = Math.max(maxarea, minheight * (j - i + 1));
            }
        }
        return maxarea;
    }
}

Approach #2 Dynamic Programming

Complexity Analysis

• Time complexity : O(N^2 * M)

• Space complexity : O(NM)

dp[i][j] 在第i行中，0 - j 列的最大宽度

class Solution {
  public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0)        return 0;
    int R = matrix.length;
    int C = matrix[0].length;
    int maxarea = 0;
    int[][] dp = new int[R][C];

    for (int i = 0; i < R; i++) {
      for (int j = 0; j < C; j++) {
        if (matrix[i][j] == '1') {
          if (j == 0) {
            dp[i][j] =  1;
          } else {
            dp[i][j] = dp[i][j - 1] + 1;
          }

          int width = dp[i][j];

          for (int k = i; k >= 0; k--) {
            width = Math.min(width, dp[k][j]);
            maxarea = Math.max(maxarea, width * (i - k + 1));
          }
        }
      }
    }
    return maxarea;
  }
}

Approach #3 Using Histograms - Stack

• Time complexity: O(n)

• Space complexity: O(n)

转化成 Leetcode 84 的单调递增栈

class Solution {
  public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) return 0;
    int maxarea = 0;
    int[] dp = new int[matrix[0].length];

    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            // update the state of this row's histogram using the last row's histogram
            // by keeping track of the number of consecutive ones
            dp[j] = matrix[i][j] == '1' ? dp[j] + 1 : 0;
        }
        // update maxarea with the maximum area from this row's histogram
        maxarea = Math.max(maxarea, leetcode84(dp));
    } 
    return maxarea;
  }

  // Get the maximum area in a histogram given its heights
  public int leetcode84(int[] heights) {
    Stack <Integer> stack = new Stack<>();
    stack.push(-1);
    int maxarea = 0;
    for (int i = 0; i < heights.length; ++i) {
      while (stack.peek() != -1 
             && heights[stack.peek()] >= heights[i]) {
        maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));
      }
      stack.push(i);
    }

    while (stack.peek() != -1) {
      maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack.peek() - 1));
    }
    return maxarea;
  }

}

Approach #4 Dynamic Programming - Maximum Height at Each

Complexity Analysis

• Time complexity : O(NM). In each iteration over N we iterate over M a constant number of times.

• Space complexity : O(M). M is the length of the additional arrays we keep.

class Solution {
  public int maximalRectangle(char[][] matrix) {
    if (matrix.length == 0) return 0;
    int m = matrix.length;
    int n = matrix[0].length;

    int[] left = new int[n]; // initialize left as the leftmost boundary possible
    int[] right = new int[n];
    int[] height = new int[n];

    Arrays.fill(right, n); // initialize right as the rightmost boundary possible

    int maxarea = 0;
    for (int i = 0; i < m; i++) {
      int cur_left = 0, cur_right = n;
      // update height
      for (int j = 0; j < n; j++) {
        if (matrix[i][j] == '1') {
          height[j]++;
        } else {
          height[j] = 0;
        }
      }
      // update left
      for (int j = 0; j < n; j++) {
        if (matrix[i][j] == '1') {
          left[j] = Math.max(left[j], cur_left);
        } else {
          left[j] = 0;
          cur_left = j + 1;
        }
      }
      // update right
      for (int j = n - 1; j >= 0; j--) {
        if (matrix[i][j] == '1') {
          right[j] = Math.min(right[j], cur_right);
        } else {
          right[j] = n; 
          cur_right = j;
        }    
      }
      // update area
      for (int j = 0; j < n; j++) {
        maxarea = Math.max(maxarea, (right[j] - left[j]) * height[j]);
      }
    }

    return maxarea;
  }
}

/*
j:0 left:0 right:1 height:1
j:1 left:0 right:5 height:0
j:2 left:2 right:3 height:1
j:3 left:0 right:5 height:0
j:4 left:0 right:5 height:0

j:0 left:0 right:1 height:2
j:1 left:0 right:5 height:0
j:2 left:2 right:3 height:2
j:3 left:2 right:5 height:1
j:4 left:2 right:5 height:1

j:0 left:0 right:1 height:3
j:1 left:0 right:5 height:1
j:2 left:2 right:3 height:3
j:3 left:2 right:5 height:2
j:4 left:2 right:5 height:2

j:0 left:0 right:1 height:4
j:1 left:0 right:5 height:0
j:2 left:0 right:5 height:0
j:3 left:3 right:4 height:3
j:4 left:0 right:5 height:0
*/

Approach #5 Divde and Conquer

Time: average case: O(n log n) Worst case: O(N^2) Space: O(n)

public class Solution {

  public int largestRectangleArea(int[] heights) {
    return calculateArea(heights, 0, heights.length - 1);
  }

  public int calculateArea(int[] heights, int start, int end) {
    if (start > end)
        return 0;
    int minindex = start;
    for (int i = start; i <= end; i++)
        if (heights[minindex] > heights[i])
            minindex = i;
    return Math.max(heights[minindex] * (end - start + 1), Math.max(calculateArea(heights, start, minindex - 1), calculateArea(heights, minindex + 1, end)));
  }

}

Better Divde and Conquer

Using a Segment Tree to find the minimum every time which can be done in O(log n) time Time: average case: O(n log n) Space: O(n)