Maximal Rectangle

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

tags: array, stack, hash table, dynamic programming

很烦leetcode的一点就是，大部分题都不给时间复杂度和空间复杂度的要求。还得自己一点点来试。

这也是我见到的tag最多的一题，难度也为hard。

先写了暴力的O(nm)^2的算法，超时。

版本一：暴力搜索，O((nm)^2)。超时

class Solution {
public:
/**
 * assume the size of 2D array is n*m.
 * this is a brute violent algorithm with the O((nm)^2) time complexity.
 * **/
 
    int maximalRectangle(vector<vector<char> > &matrix) {
        //handle empty input
        if(matrix.empty()){
            return 0;
        }
        
        int maxArea = 0;
        int height = matrix.size();
        int length = matrix[0].size();
        
        //(sx, sy) is the left-top corner of a possible rectangle 
        for(int sy = 0; sy < height; sy++){
            for(int sx = 0; sx < length; sx++){
                if(matrix[sy][sx] == '1'){
                    
                    //(x,y) is the right-bottom corner of a possible rectangle
                    int maxLength = length;
                    for(int y = sy; y < height; y++){
                        for(int x = sx; x < length; x++){
                            if(matrix[y][x] == '0' || x - sx + 1 == maxLength){
                                
                                //update maxLength
                                maxLength = x - sx + 1;
                                int thisArea = (x - sx + 1) * (y - sy + 1);
                                maxArea = max(maxArea, thisArea);
                            }
                        }
                    }
                }
            }
        }
    
        return maxArea;
    }
};

我想写分治算法的，就是分别求出子区域的最大矩形面积，然后再求邻接边界的最大矩形面积，再拼出一个跨边界的矩形，算三者的最大值。但感觉很麻烦，尤其是拼矩形时的算法。

看了discussion，有人晒出了O(nm)的代码。利用了stack，并压缩了原始矩阵，还在学习中，稍候更新。

一月二十四日更新

版本二：o(mn). 动态规划，栈。

这个版本有点奇技淫巧。不够clean，但是能AC，还在尝试优化。

新建一个与原题一样大小的矩阵，每个单元格表示，从包括该单元格开始向上查的连续的1的个数。

也就是变成了矩形高度的直方图。

1010        1010
1011    =>  2021
1011    =>  3032
1111        4143

建完该矩阵后，开始扫每一行。并维护一个栈。栈里存储的是，可能的最大矩形的左下角的位置。算法保证了栈中的元素是递增的。当扫到每行的末尾时，计算栈里每个元素代表的矩阵大小，把栈清空。

比较难理解，这个方法不够清晰。尝试优化中。

更新：

原来这个是有特定算法的。求直方图中的最大面积：

http://blog.csdn.net/havenoidea/article/details/11854723

那这个算法就不算是奇技淫巧了阿～～哇哈哈。AC

class Solution {
public:
/**
 * O(nm)
 **/
    int maximalRectangle(vector<vector<char> > &matrix) {
       
        if(matrix.empty()){
            return 0;
        }
        
        int height = matrix.size();
        int length = matrix[0].size();
        int maxArea = 0;
        //s stores possible left-bottom start corner. 
        stack<int> s;
        
        //map stores the current rectangle height of current column.
        int map[height][length];
        
        for(int i = 0; i < length; i++){
            map[0][i] = matrix[0][i] == '1'?1:0;
        }
        
        for(int j = 1; j < height; j++){
            for(int i = 0; i < length; i++){
                map[j][i] = matrix[j][i] == '1'?map[j - 1][i] + 1:0;
            }
        }
        
        for(int i = 0; i < height; i++){
            int j = 0;
            while(j != length){
                if(s.empty()){
                    s.push(j);
                    j++;
                }
                
                //s is not empty
                else{
                    if (map[i][j] >= map[i][s.top()]){
                        s.push(j);
                        j++;
                    }
                    //map[i][j] < the top of stack
                    else{
                        while(map[i][j] < map[i][s.top()]){
                            int t = s.top();
                            s.pop();
                            int start = s.empty()?-1:s.top();
                            int thisArea = map[i][t] * (j - start - 1);
                            maxArea = max(thisArea, maxArea);
                            if (s.empty()){
                                break;
                            }
                        }
                        //push j into the stack, now map[i][j] >= the top of stack 
                        
                        
                    }
                }
            }
            // j == length , at the end of the row
            while(!s.empty()){
                int t = s.top();
                s.pop();
                int start = s.empty()?-1:s.top();
                int thisArea = map[i][t] * (length - start - 1);
                maxArea = max(thisArea, maxArea);
            }
        }
        return maxArea;
    }
};