LeetCode1504. Count Submatrices With All Ones

一、题目

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

Example 1:

Input: mat = [[1,0,1],[1,1,0],[1,1,0]]
Output: 13
Explanation:
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2.
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.
Example 2:

Input: mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
Output: 24
Explanation:
There are 8 rectangles of side 1x1.
There are 5 rectangles of side 1x2.
There are 2 rectangles of side 1x3.
There are 4 rectangles of side 2x1.
There are 2 rectangles of side 2x2.
There are 2 rectangles of side 3x1.
There is 1 rectangle of side 3x2.
Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.

Constraints:

1 <= m, n <= 150
mat[i][j] is either 0 or 1.

二、题解

class Solution {
public:int numSubmat(vector<vector<int>>& mat) {int res = 0;int m = mat.size(),n = mat[0].size();vector<int> heights(n,0);for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){heights[j] = mat[i][j] == 0 ? 0 : heights[j] + 1;}res += countFromBottom(heights);}return res;}int countFromBottom(vector<int>& heights){int n = heights.size();int res = 0;stack<int> st;for(int i = 0;i < n;i++){while(!st.empty() && heights[i] <= heights[st.top()]){int cur = st.top();st.pop();if(heights[cur] > heights[i]){int left = st.empty() ? -1 : st.top();int len = i - left - 1;int bottom = max(left == -1 ? 0 : heights[left],heights[i]);res += (heights[cur] - bottom) * len * (len + 1) / 2;}}st.push(i);}while(!st.empty()){int cur = st.top();st.pop();int left = st.empty() ? -1 : st.top();int len = n - left - 1;int bottom = left == -1 ? 0 : heights[left];res += (heights[cur] - bottom) * len * (len + 1) / 2;}return res;}
};