Why my code failed with run time error?


  • 0
    U
    #include <iostream>
    #include <vector>
    #include <stack>
    using namespace std;
    
    class Solution {
    public:
        int maximalRectangle(vector<vector<char> > &matrix) {
    	int r = matrix.size();
    	if (!r) return 0;
    	int c = matrix[0].size();
    	vector<vector<int> > v;
    	//init
    	v.resize(r);
    	for (int i = 0; i<r ; i++) {
    	    v[i].resize(c);
    	    for (int j = 0; j<c; j++){
    		if (i==0) {
    		    v[i][j] = (matrix[i][j] - '0');
    		} else {
    		    v[i][j] = v[i-1][j] + (matrix[i][j] - '0');
    		}
    	    }
    	}
    
    	//histogram
    	int maxRac = 0;
    	for (int i = 0; i<r; i++) {
    	    int Rac = histogram(v[i]);
    	    maxRac = max(maxRac, Rac);
    	}
    	return maxRac;
        }
    private:
        int histogram(vector<int>& v) {
    	stack<int> s;
    	int maxr = 0;
    	for (int i = 0; i<v.size(); i++) {
    	    if (s.empty() || v[i]>s.top()) {
    		s.push(i);
    	    } else {
    		while (v[i]<=s.top()) {
    		    int top = s.top();
    		    s.pop();
    		    maxr = max(maxr, s.empty() ? v[top]*i  : v[top]*(i-1-s.top()));
    		}
    		s.push(i);
    	    }
    	}
    	while (!s.empty()) {
    	    int len = v.size();
    	    int top = s.top();
    	    s.pop();
    	    maxr = max(maxr, s.empty() ? v[top]*len : v[top]*(len-1-s.top()));
    	}
    	return maxr;
        }
    };
    
    
    
    int main() {
        Solution s;
        vector<vector<char> > m;
        vector<char> v;
        v.push_back('1');
        v.push_back('0');
        m.push_back(v);
        cout<<m[0][0]<<' '<<m[0][1]<<endl;
        cout<<s.maximalRectangle(m)<<endl;
    }

  • 0
    D
       while (!s.empty()) {
            int len = v.size();
            int top = s.top();
            s.pop();
            maxr = max(maxr, s.empty() ? v[top]*len : v[top]*(len-1-s.top()));
        }
    

    Here in some cases, s.pop(); makes the stack empty and (v[i]<=s.top()) still tries to access the top node


Log in to reply
 

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