1504. Count Submatrices With All Ones

Given an m x n binary matrix mat, return the number of submatrices that have all ones.

• optimize ref : Largest Rectangle in Histogram

class Solution {
    int helper(vector<int>& dp) {
        vector<int> st;
        vector<int> sum(dp.size(), 0);

        for(int i = 0; i < dp.size(); i++) {
            while(!st.empty() and dp[st.back()] >= dp[i]) st.pop_back();
            if(st.empty()) {
                sum[i] = dp[i] * (i + 1);
            } else {
                sum[i] += sum[st.back()];
                sum[i] += dp[i] * (i - st.back());
            }
            st.push_back(i);
        }

        return accumulate(sum.begin(), sum.end(), 0);
    }
public:
    int numSubmat(vector<vector<int>>& mat) {
        int n = mat.size(), m = mat[0].size();
        vector<int> dp(m, 0);
        int res = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                dp[j] = (mat[i][j] ? dp[j] + 1 : 0);
            }
            res += helper(dp);
        }

        return res;
    }
};