leetcode 1504. Count Submatrices With All Ones | 1504. 统计全 1 子矩形（单调栈）

待我称王封你为后i 2022-09-15 05:41 108阅读 0赞

## 题目 ##

[https://leetcode.com/problems/count-submatrices-with-all-ones/][https_leetcode.com_problems_count-submatrices-with-all-ones]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

本题与 [leetcode 84. Largest Rectangle in Histogram | 84. 柱状图中最大的矩形（单调栈）][leetcode 84. Largest Rectangle in Histogram _ 84.] 思路相似，借鉴了原来的代码。

以及类似问题：[leetcode 85. Maximal Rectangle | 85. 最大矩形（单调栈）][leetcode 85. Maximal Rectangle _ 85.]

class Solution { 
        public int numSubmat(int[][] mat) { 
            if (mat.length == 0) return 0;
            int M = mat.length;
            int N = mat[0].length;
    
            int[][] heights = new int[M][N]; // 上方有多少个连续的1
            for (int i = 0; i < N; i++) { 
                heights[0][i] = mat[0][i] - 0;
                for (int j = 1; j < M; j++) { 
                    if (mat[j][i] == 1) heights[j][i] = heights[j - 1][i] + 1;
                    else heights[j][i] = 0;
                }
            }
    
            int result = 0;
            for (int i = 0; i < M; i++) { 
                result += countRectangle(heights[i]);
            }
            return result;
        }
    
    
        // Reference:
        // leetcode 84. Largest Rectangle in Histogram
        // leetcode 85. Maximal Rectangle
        public int countRectangle(int[] heights) { 
            int L = heights.length;
            // 找左边第一个小于h[i]的数
            // 从右向左遍历，维护单调不减栈，小数h[i]不断将大数h[j]弹出，则h[i]左边第一个小于h[i]的数为h[j]
            Stack<Integer> valueStack = new Stack<>();
            Stack<Integer> indexStack = new Stack<>();
            int[] leftIndex = new int[L]; // i左边第一个小于i的数的下标
            Arrays.fill(leftIndex, -1);
            for (int i = L - 1; i >= 0; i--) { 
                while (!valueStack.isEmpty() && valueStack.peek() > heights[i]) { 
                    leftIndex[indexStack.pop()] = i;
                    valueStack.pop();
                }
                valueStack.push(heights[i]);
                indexStack.push(i);
            }
            // 找右边第一个小于h[i]的数
            // 从左向右遍历，维护单调不减栈
            valueStack = new Stack<>();
            indexStack = new Stack<>();
            int[] rightIndex = new int[L]; // i右边第一个小于i的数的下标
            Arrays.fill(rightIndex, L);
            for (int i = 0; i < L; i++) { 
                while (!valueStack.isEmpty() && valueStack.peek() > heights[i]) { 
                    rightIndex[indexStack.pop()] = i;
                    valueStack.pop();
                }
                valueStack.push(heights[i]);
                indexStack.push(i);
            }
    
            // 对于每个h[i]，以当前高度分别向左右扩张，计算整个大区域的长方形个数
            int totalRectangle = 0;
            boolean[][] seen = new boolean[L + 2][L + 2]; // from,to
            for (int i = 0; i < L; i++) { 
                if (seen[leftIndex[i] + 1][rightIndex[i] + 1]) continue; // 相同高度只需计算一次
                else seen[leftIndex[i] + 1][rightIndex[i] + 1] = true;
    
                int leftHeight = leftIndex[i] >= 0 ? heights[leftIndex[i]] : 0; // 左边第一个小于h[i]的高度
                int rightHeight = rightIndex[i] < L ? heights[rightIndex[i]] : 0; // 右边第一个小于h[i]的高度
    
                int validHeight = heights[i] - Math.max(leftHeight, rightHeight); // 自由的高度
                int validWidth = rightIndex[i] - leftIndex[i] - 1; // 自由的宽度
    
                if (heights[i] > 0) totalRectangle += (validWidth * (validWidth + 1) / 2) * validHeight;
            }
            return totalRectangle;
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[https_leetcode.com_problems_count-submatrices-with-all-ones]: https://leetcode.com/problems/count-submatrices-with-all-ones/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/4fcd8b71ac2845bf9aeab96173563194.png
[leetcode 84. Largest Rectangle in Histogram _ 84.]: https://hanquan.blog.csdn.net/article/details/120302405
[leetcode 85. Maximal Rectangle _ 85.]: https://blog.csdn.net/sinat_42483341/article/details/120326122
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/0824a96b4e354e68a5305ca965de7f64.png