Leetcode 85. Maximal Rectangle

Problem

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

Think

这个问题对我而言还是有一点难度的，主要参考了youtube上的一个视频：https://www.youtube.com/watch?v=g8bSdXCG-lA&t=71s
这个问题解答可以分解为两个步骤，在这之前需要考虑一个叫做
max Area Rectangle in histogram的问题（直方图中最大的矩形面积）
这个问题的描述用一个图还是一目了然的，不需要太多解释．

image.png
现在我们假设解决了max Area Rectangle in histogram，现在考虑怎么解决本来需要解决的问题．
　　现在有输入数据：

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

• 用一个dp数组保存＂直方图＂数据,数组的大小与行同长(len(dp) == 5)　dp[i]可以理解为以第i 行为x轴绘制的直方图纵轴高度数据．
• 依照行循环
  　第1次循环 dp[0] = [1,0 ,1, 0, 0 ]
  第２次：　dp[1] = [2, 0, 2, 1, 1]
  　第３次： dp[2] = [3, 1, 2, 2, 2]
  　第４次： dp[3] = [4, 0, 0, 3, 0]
• 依次计算上述四次循环中dp数据的max Area Rectangle in histogram值，四次循环中的最大值就是最终答案

max Area Rectangle in histogram　问题

这个问题其实也并不简单，特别是如果要用O(N)复杂度解决问题的话，还是比较考验智商的．
关于这个问题的解决方案可以参考：
http://www.geeksforgeeks.org/largest-rectangle-under-histogram/
这个是一个非常巧妙的解决方案，基本思想是使用stack

// The main function to find the maximum rectangular area under given
// histogram with n bars
int getMaxArea(int hist[], int n)
{
    // Create an empty stack. The stack holds indexes of hist[] array
    // The bars stored in stack are always in increasing order of their
    // heights.
    stack<int> s;
 
    int max_area = 0; // Initalize max area
    int tp;  // To store top of stack
    int area_with_top; // To store area with top bar    as the smallest bar
 
    // Run through all bars of given histogram
    int i = 0;
    while (i < n)
    {
        // If this bar is higher than the bar on top stack, push it to stack
        if (s.empty() || hist[s.top()] <= hist[i])
            s.push(i++);
        // If this bar is lower than top of stack, then calculate area of rectangle 
        // with stack top as the smallest (or minimum height) bar. 'i' is 
        // 'right index' for the top and element before top in stack is 'left index'
        else
        {
            tp = s.top();  // store the top index
            s.pop();  // pop the top
            cout<<"the top is:"<<hist[tp]<<endl;
            // Calculate the area with hist[tp] stack as smallest bar
            area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
            cout<<"max area:"<<area_with_top<<endl;
            // update max area, if needed
            if (max_area < area_with_top)
                max_area = area_with_top;
        }
    }
 
    // Now pop the remaining bars from stack and calculate area with every
    // popped bar as the smallest bar
    while (s.empty() == false)
    {
        tp = s.top();
        s.pop();
        cout<<"top is:"<<hist[tp]<<endl;
        area_with_top = hist[tp] * (s.empty() ? i : i - s.top() - 1);
        cout<<"area:"<<area_with_top<<endl;
        if (max_area < area_with_top)
            max_area = area_with_top;
    }
 
    return max_area;
}
int main(){
int hist[] = {4,2,5,3,1,6};
    int n = sizeof(hist)/sizeof(hist[0]);
    cout << "Maximum area is " << getMaxArea(hist, n)<<endl;
    return 0;
}

参考资源：https://www.youtube.com/watch?v=KkJrGxuQtYo
这里所使用的原理是：　对于每一个高度，计算在这个高度上能够达到的最大面积值，然后在这些最大面积值中进行比较，得出最终结果．在某一个高度上能够带到的最大面积由＂边界＂决定，所谓边界指的是两边的高度都比指定高度要低．

Code

class Solution(object):
    
    def maxAreaRectangle(self, seq):
        # type(seq): list(int)
        # list[i] represent height at i
        max_area = -1
        i = 0
        stack = []
        while i < len(seq):
            if len(stack) == 0 or seq[stack[-1]] <= seq[i]:
                stack.append(i)
                i += 1
            else:
                tp = stack.pop()
                area_with_top = seq[tp] * (i if len(stack) == 0 else (i - stack[-1] - 1))
                if area_with_top > max_area:
                    max_area = area_with_top
        while len(stack) > 0:
            tp = stack.pop()
            area_with_top = seq[tp] * (i if len(stack) == 0 else (i - stack[-1] - 1))
            if area_with_top > max_area:
                max_area = area_with_top
        return max_area

    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        m = len(matrix)
        if m == 0:
            return 0
        n = len(matrix[0])
        ans = -1
        dp = []
        for i in range(m):
            if i == 0:
                for j in range(n):
                    dp.append(int(matrix[i][j]))
            else:
                new_dp = []
                for j in range(n):
                    if dp[j] != 0 and matrix[i][j] == '1':
                        new_dp.append(dp[j] + 1)
                    else:
                        new_dp.append(int(matrix[i][j]))
                dp = new_dp
            level_max = self.maxAreaRectangle(dp)
            if level_max > ans:
                ans = level_max
        return ans
```