The input "01", I get the right answer 1 on my machine but it tells that I output 0, could somebody tell me why?


  • 0
    H

    class Solution {
    public:
    int maximalRectangle(vector<vector<char>>& matrix) {
    int row = matrix.size();
    if(row == 0)
    return 0;
    int col = matrix[0].size();
    if(col == 0)
    return 0;

    	int* dpheight = new int[col];
    	for(int i=0; i<col; i++) 
    		dpheight[i] = 0;
    
    	int ret = 0;
    	for(int i=0; i<row; i++) {
    		// 先动态更新每一列在以该行为底的高度
    		for(int j=0; j<col; j++) {
    			if(matrix[i][j] == '0')
    				dpheight[j] = 0;
    			else
    				dpheight[j]++;
    		}
    		ret = max(ret, maxAreaOfHistol(dpheight, col));
    	}
    	return ret;
    }
    
    int maxAreaOfHistol(int* height, int col) {
    	stack<int> s;
    	s.push(0);
    	int ret = 0;
    	for(int i=0; i<col+1; i++) {
    		if(s.empty() || (!s.empty() && height[i] > height[s.top()]))
    			s.push(i);
    		else {
    			while(!s.empty() && height[s.top()] > height[i]) {
    				int tmp = s.top();
    				s.pop();
    				ret = max(ret, height[tmp] * (s.empty() ? i : i - s.top() - 1));
    			}
    			s.push(i);
    		}
    	}
    	return ret;
    }
    

    };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.