1504

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int rows=mat.size(), cols=mat[0].size();
        vector<int> h(cols+1);

        int ans = 0;
        // Have the histogram heights.
        for(int i=0; i<rows; i++){
            for(int j=0; j<cols; j++)
                h[j] = (mat[i][j]) ? h[j]+1 : 0;

            // Get all rectangles that reside on current row.
            ans += countSubmatrices(h);
        }
        return ans;
    }

    int countSubmatrices(vector<int> &h){
        int n=h.size(), ans=0;
        stack<int> stk;
        vector<int> sum(n, 0);
        for(int i=0; i<n; i++){
            while(!stk.empty() && h[stk.top()] >= h[i])
                stk.pop();
            if(!stk.empty()){
                sum[i] = sum[stk.top()]; // Init to first height smaller than current.
                sum[i] += h[i]*(i-stk.top()); // All rectangle possible with heights greater than current.
            }
            else{
                sum[i] = h[i]*(i+1); // If stack is empty, consider all heights.
            }
            ans += sum[i];
            stk.push(i);
        }
        return ans;
    }

};