3359. Find Sorted Submatrices With Maximum Element at Most K
You are given a 2D matrix grid
of size m x n
. You are also given a non-negative integer k
.
Return the number of submatrices of grid
that satisfy the following conditions:
- The maximum element in the submatrix less than or equal to
k
.
- Each row in the submatrix is sorted in non-increasing order.
A submatrix (x1, y1, x2, y2)
is a matrix that forms by choosing all cells grid[x][y]
where x1 <= x <= x2
and y1 <= y <= y2
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| class Solution { public: long long countSubmatrices(vector<vector<int>>& grid, int k) { long long res = 0, n = grid.size(), m = grid[0].size(); grid.push_back(vector<int>(m,k + 1)); vector<vector<pair<long long, long long>>> dp(m); auto clean = [&](int x) { int t = 0; for(int i = 0; i < dp[x].size(); i++) { int h = dp[x].back().first - dp[x][i].first; res += h * (h + 1) / 2 * (dp[x][i].second - t); t = dp[x][i].second; } dp[x] = {}; }; for(int i = 0; i <= n; i++) { for(long long j = 0, len = 0; j < m; j++) { if(grid[i][j] > k) { dp[j].push_back({i,0}); clean(j), len = 0; } else { if(!j or grid[i][j] <= grid[i][j-1]) len++; else len = 1; int pos = i; while(dp[j].size() and dp[j].back().second > len) { long long h = i - dp[j].back().first; long long w = dp[j].back().second - max(len, dp[j].size() > 1 ? dp[j][dp[j].size()-2].second : 0); res += h * (h + 1) / 2 * w; pos = dp[j].back().first; dp[j].pop_back(); } if(dp[j].size() == 0 or dp[j].back().second != len) { dp[j].push_back({pos,len}); } } } } return res; } };
|