Mycode WA but do not know why?


  • 0
    R
    class Solution {
    public:
        vector<vector<char>> a;
        int m, n;
        int maximalRectangle(vector<vector<char>>& a_) {
            a = a_;
            m=a.size(), n = m ? a[0].size() : 0;
            if(!m || !n) return 0;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++) a[i][j]-='0';
            }
            for(int i=1;i<m;i++){
                for(int j=0;j<n;j++) a[i][j]+=a[i-1][j];
            }
            int ans = 0;
            for(int i=0;i<m;i++){
                ans=max(ans, f(i));
            }
            return ans;
        }
        int f(int row){
            stack<int> st;
            int left[n];
            for(int j=0;j<n;){
                if(st.empty()){
                    left[j]=0;
                    st.push(j++);
                }else if(a[row][st.top()]<a[row][j]){
                    left[j]=st.top()+1;
                    st.push(j++);
                }else{
                    st.pop();
                }
            }
            stack<int> st1;
            int right[n];
            for(int j=n-1;j>=0;){
                if(st1.empty()){
                    right[j]=n-1;
                    st1.push(j--);
                }else if(a[row][st1.top()]<a[row][j]){
                    right[j]=st1.top()-1;
                    st1.push(j--);
                }else{
                    st1.pop();
                }
            }
            int ans = 0;
            for(int j=0;j<n;j++){
                ans=max(ans, a[row][j] * (right[j]-left[j]+1));
            }
            return ans;
        }
    };
    

    Below is right answer

    class Solution {
    public:
      vector<vector<char>> a;
      int m, n;
      int maximalRectangle(vector<vector<char>>& a_) {
        a = a_;
        m=a.size(), n = m ? a[0].size() : 0;
        if(!m || !n) return 0;
        for(int i=0; i<m; i++) {
          for(int j=0; j<n; j++) a[i][j]-='0';
        }
        for(int i=1; i<m; i++) {
          for(int j=0; j<n; j++) {
            if(a[i][j]) {
              a[i][j]+=a[i-1][j];
            }
          }
        }
        int ans = 0;
        for(int i=0; i<m; i++) {
          ans=max(ans, f(i));
        }
        return ans;
      }
      int f(int row) {
        stack<int> st;
        int left[n];
        for(int j=0; j<n;) {
          if(st.empty()) {
            left[j]=0;
            st.push(j++);
          } else if(a[row][st.top()]<a[row][j]) {
            left[j]=st.top()+1;
            st.push(j++);
          } else {
            st.pop();
          }
        }
        stack<int> st1;
        int right[n];
        for(int j=n-1; j>=0;) {
          if(st1.empty()) {
            right[j]=n-1;
            st1.push(j--);
          } else if(a[row][st1.top()]<a[row][j]) {
            right[j]=st1.top()-1;
            st1.push(j--);
          } else {
            st1.pop();
          }
        }
        int ans = 0;
        for(int j=0; j<n; j++) {
          ans=max(ans, a[row][j] * (right[j]-left[j]+1));
        }
        return ans;
      }
    };

  • 0
    S

    ["101","000","101"]
    the case answer is error


  • 0
    R

    Really thanks for your useful case to help me find my bugs.
    When I construct continoues histograms, I forget to check whether current is 1, only 1 should add previous line summation, otherwise is wrong.


Log in to reply
 

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