leetcode221 Maximal Square

题目链接

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

开始是用单调栈做的，出问题的代码在这

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0)
            return 0;
        int row = matrix.size();
        for(int i = 0; i < row; i++)
        {
            matrix[i].push_back(\'0\');
        }
        int column = matrix[0].size();
        stack<int> S;
        int result = 0;
        int t = 0;
        int width = 0;
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < column; j++)
            {
                if(i > 0 && matrix[i][j] > \'0\' && matrix[i-1][j] > \'0\')
                    matrix[i][j] += (matrix[i-1][j] - \'0\');
                while(!S.empty() && matrix[i][j] <= matrix[i][S.top()])
                {
                    t = S.top();
                    S.pop();
                    if(S.empty())
                        width = j;
                    else
                        width = j - S.top() - 1;
                    int height = matrix[i][t] - \'0\';
                    if(width <= height)
                        result = max(result, width*width);
                    else
                        result = max(result, height*height);
                }
                if(j < column-1)
                    S.push(j);
            }
            if(!S.empty())
                cout << i << endl;
        }
        return result;
    }
};

这题开始使用的单调栈做的，一直最后一个测试用例通不过，一查发现是

if(j < column - 1)
    S.push(j);

这行出错的

换成

while(!S.empty())
    S.pop();

就好了 

这就很奇怪了，我明明设置了 matrix[i][j] <= matrix[i][S.top()]的时候S.pop()啊

最后发现，问题出在这一行

if(i > 0 && matrix[i][j] > \'0\' && matrix[i-1][j] > \'0\')
    matrix[i][j] += (matrix[i-1][j] - \'0\');

当matrix的行数列数很多的时候，很有可能matrix[i][j]累加就超过127了（char的最大长度）

这个时候matrix[i][j] < 0, 不会被弹出（好sb的错误。。。）

换成动态规划就好了

AC代码

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0)
            return 0;
        int row = matrix.size();
        int column = matrix[0].size();
        vector<vector<int> > dp(row, vector<int>(column, 0));
        int result = 0;
        dp[0][0] = matrix[0][0] == \'0\' ? 0 : 1;
        result = max(dp[0][0], result);
        for(int i = 1; i < row; i++)
        {
            dp[i][0] = matrix[i][0]==\'1\' ? 1 : 0;
            result = max(dp[i][0], result);
        }
        for(int j = 1; j < column; j++)
        {
            dp[0][j] = matrix[0][j]==\'1\' ? 1 : 0;
            result = max(result, dp[0][j]);
        }
        for(int i = 1; i < row; i++)
            for(int j = 1; j < column; j++)
            {
                dp[i][j] = matrix[i][j] == \'0\' ? 0 :1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]));
                result = max(result, dp[i][j]);
            }
        return result*result;
    }
};