It complains error. Can you see what's wrong?


  • -3
    W

    Here is the idea: (refer from http://www.cnblogs.com/lichen782/p/leetcode_maximal_rectangle.html)

    1. For each row, compute the continuous '1' number which is adjacent above.
    2. For each row, apply the max adjacent rectangle area to compute.
    3. The largest one is the result.

    Question: It looks there is one-off error. Can you see it?

    Submission Result: Wrong Answer

    Input: ["01101","11010","01110","11110","11111","00000"]
    Output: 8
    Expected: 9

    class Solution { public:
        int maximalRectangle(vector<vector<char> > &matrix) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            int maxArea = 0;
            if (matrix.size() == 0) return 0;
            
            vector<int> hist(matrix[0].size(),0);
            
            for (int row=0; row< matrix.size(); row++)
            {
                //compute hist.
                for (int col=0; col<matrix[0].size();col++)
                {
                    if (matrix[row][col] == '0') {
                        hist[col] = 0;
                    }else{
                        hist[col] += 1;
                    }
                }
                
                //get max history rectangle size
                maxArea = max(maxArea, maxRectHistArea(matrix, hist));
            }
            
            return maxArea;
        }
         private:
        int maxRectHistArea(vector<vector<char> > &matrix, vector<int> &hist)
        {
            stack<int> S; //store array index;
            int maxArea = INT_MIN;
            
            for (int i=0; i<hist.size(); i++)
            {
                if (S.empty()) {
                    S.push(i);
                    continue;
                }
                
                while(!S.empty() && hist[S.top()] > hist[i]) {
                    int index = S.top();
                    S.pop();
                    
                    int area = (i - index)*hist[index];
                    if (area > maxArea) maxArea = area;
                }
                
                S.push(i);
            }
            
            //clean stack
            while(!S.empty()){
                int area = (hist.size() - S.top())*hist[S.top()];
                if (area > maxArea) maxArea = area;
                S.pop();
            }
            
            return maxArea;
        } };
    

    Figure out the root cause. We have to save both index and height information into stack somehow. Here is working one.

    class Solution {
    public:
        int maximalRectangle(vector<vector<char> > &matrix) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            int maxArea = 0;
            if (matrix.size() == 0) return 0;
            
            vector<int> hist(matrix[0].size(),0);
            
            for (int row=0; row< matrix.size(); row++)
            {
                //compute hist.
                for (int col=0; col<matrix[0].size();col++)
                {
                    if (matrix[row][col] == '0') {
                        hist[col] = 0;
                    }else{
                        hist[col] += 1;
                    }
                }
                
                //get max hist rectangle area
                maxArea = max(maxArea, largestRectangleArea(hist));
            }
            
            return maxArea;
        }
        
    public:
        struct Item{
            int index;
            int height;
            Item(int i,int h):index(i),height(h){};
            Item():index(-1),height(0){};
        };
        
    
    private:
        int largestRectangleArea(vector<int> &height) {
            stack<Item> S;
            int N = height.size();
            int area = 0;
            
            for (int i=0; i<N; i++)
            {
                if (S.empty()) {
                    S.push(Item(i,height[i]));
                    continue;
                }
                
                //compare
                if (height[i] < S.top().height){
                    //pop till empty or smaller item appear
                    Item item;
                    while (!S.empty() && S.top().height > height[i]) {
                        item = S.top();
                        S.pop();
                        
                        area = max(area, (i - item.index)*item.height);
                    }
                    
                    //push. Pay attention to the index
                    S.push(Item(item.index, height[i]));
                }else{
                    S.push(Item(i,height[i]));
                }
            }
            
            //stack maybe not empty yet
            while(!S.empty()){
                Item item = S.top(); S.pop();
                area = max(area, (N - item.index)*item.height);
            }
            
            return area;
        }
    };

  • 0

    You need to show that you have done minimal research before asking a question. Please read the FAQ for guidelines on how to ask a question.


  • 0
    W

    Sorry that I should be more specific. I followed the method http://www.cnblogs.com/lichen782/p/leetcode_maximal_rectangle.html

    But my implementation seems has a bug there while I can't find it by code review. I didn't use debugger to debug it out because I think it's another way towards interview preparation.


  • 0
    S

    The link is not ok. You should explain your algorithm in some words and add comment in your code. When you do it, just edit your question, do not reply in comment. Thanks!


  • 0
    W

    I figure out the problem. The problem is we have to save both index and height in the stack. Here is working one.


  • 0
    B

    No, you only need store the indices on the stack. You can get the corresponding heights from the input vector.


Log in to reply
 

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