Leetcode - Maximal Rectangle

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

Solution from leetcode article:

Intuition

Imagine an algorithm where for each point we computed a rectangle by doing the following:

• Finding the maximum height of the rectangle by iterating upwards until a 0 is reached

• Finding the maximum width of the rectangle by iterating outwards left and right until a height that doesn't accommodate the maximum height of the rectangle

We know that the maximal rectangle must be one of the rectangles constructed in this manner.

Given a maximal rectangle with height h, left bound l, and right bound r, there must be a point on the interval [l, r] on the rectangle's base where the number of consecutive ones (height) above the point is <=h. If this point exists, then the rectangle defined by the point in the above manner will be the maximal rectangle, as it will reach height h iterating upward and then expand to the bounds of [l, r] as all heights within those bounds must accommodate h for the rectangle to exist.

If this point does not exist, then the rectangle cannot be maximum, as you would be able to create a bigger rectangle by simply increasing the height of original rectangle, since all heights on the interval [l, r] would be greater than h.

As a result for each point you only need to compute h, l, and r - the height, left bound, and right bound of the rectangle it defines.

Using dynamic programming, we can use the h, l, and r of each point in the previous row to compute the h, l, and r for every point in the next row in linear time.

Algorithm

Given row matrix[i], we keep track of the h, l, and r of each point in the row by defining three arrays - height, left, and right.

height[j] will correspond to the height of matrix[i][j], and so on and so forth with the other arrays.

The question now becomes how to update each array.

Height:

This one is easy. h is defined as the number of continuous ones in a line from our point. We explored how to compute this in Approach 2 in one row with:

row[j] = row[j - 1] + 1 if row[j] == '1'

We can just make a minor modification for it to work for us here:

new_height[j] = old_height[j] + 1 if row[j] == '1' else 0

Left:

Consider what causes changes to the left bound of our rectangle. Since all instances of zeros occurring in the row above the current one have already been factored into the current version of left, the only thing that affects our left is if we encounter a zero in our current row.

As a result we can define:

new_left[j] = max(old_left[j], cur_left)

cur_left is one greater than rightmost occurrence of zero we have encountered. When we "expand" the rectangle to the left, we know it can't expand past that point, otherwise it'll run into the zero.

Right:

Here we can reuse our reasoning in left and define:

new_right[j] = min(old_right[j], cur_right)

cur_right is the leftmost occurrence of zero we have encountered. For the sake of simplicity, we don't decrement cur_right by one (like how we increment cur_left) so we can compute the area of the rectangle with height[j] * (right[j] - left[j]) instead of height[j] * (right[j] + 1 - left[j]).

This means that technically the base of the rectangle is defined by the half-open interval [l, r) instead of the closed interval [l, r], and right is really one greater than right boundary. Although the algorithm will still work if we don't do this with right, doing it this way makes the area calculation a little cleaner.

Note that to keep track of our cur_right correctly, we must iterate from right to left, so this is what is done when updating right.

With our left, right, and height arrays appropriately updated, all that there is left to do is compute the area of each rectangle.

Since we know the bounds and height of rectangle j, we can trivially compute it's area with height[j] * (right[j] - left[j]), and change our max_area if we find that rectangle j's area is greater.

func maximalRectangle(matrix [][]byte) int {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return 0
    }
    m := len(matrix)
    n := len(matrix[0])
    
    height := make([]int, n)
    left := make([]int, n)
    right := make([]int, n)
    for i := 0; i < len(right); i++ {
        right[i] = n
    }
    
    maxArea := 0
    for i := 0; i < m; i++ {
        curLeft := 0
        curRight := n
        for j := 0; j < n; j++ {
            if matrix[i][j] == '1' {
                height[j]++
            } else {
                height[j] = 0
            }
        }
        for j := 0; j < n; j++ {
            if matrix[i][j] == '1' {
                left[j] = max(left[j], curLeft)
            } else {
                left[j] = 0
                curLeft = j+1
            }
        }
        for j := n-1; j >= 0; j-- {
            if matrix[i][j] == '1' {
                right[j] = min(right[j], curRight)
            } else {
                right[j] = n
                curRight = j
            }
        }
        for j := 0; j < n; j++ {
            maxArea = max(maxArea, (right[j]- left[j])*height[j])
        }
    }
    
    return maxArea
}

func max(a, b int) int{
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

• 相关文章
• 全局相关文章