leetcode：1504. 统计全 1 子矩形的个数

题目来源

• leetcode

题目描述

class Solution {
    
public:
    int numSubmat(vector<vector<int>>& mat) {
    

    }
};

题目解析

问题：

• 必须以第0行为底的矩阵，其内部全是1的有多少个
• 必须以第1行为底的矩阵，其内部全是1的有多少个
• 必须以第2行为底的矩阵，其内部全是1的有多少个
• …
• 然后将上面的全部加起来，就是答案

举个例子：

• 必须以第0行为第的矩阵，其内部全是1的子矩阵有：
  • {a}、{b}、{a，b]
  • 一共3个
• 必须以第1行为底的矩阵，其内部全是1的有多少个
  • {c}、{d}、{c，d}、{a，c}、{b，d}、{a，b，c，d}

那，以某一行为底的矩阵，其内部全是1的有多少个，应该怎么求呢？

• 在求以某一行打底时，可以按照数组直方图的思路，将当前行连同上面各行的数据处理下列，形成一个直方图，然后拿着直方图数组，去求个数
• 拿数组直方图求答案时，【单调栈】：
  • 统计每个位置index，左侧比自己小、离自己最近的元素位置 leftIndex；
  • 右侧比自己小、离自己最近的元素位置 rightIndex；
  • 则，形成的数组直方图长度L = rightIndex - leftIndex + 1
  • 如果只考虑当前打底行，个数 = L + (L-1) + (L - 2) + … + 1 = (L * (L + 1))/2；
  • 还需要考虑直方图的高度 h ，总个数 = h * ((L * (L + 1))/2)；
  • 但这样会重复，为了避免重复，这里的 h = [index] - max([leftIndex], [rightIndex])； ??? （待补充）
• 所以，计算公式 = ( (L * (L + 1))/2 ) * ( [index] - max([leftIndex], [rightIndex]) )

class Solution {
    
    // 计算以某一行打底（形成的直方图数组height）的全1子矩阵的数量
    int process(std::vector<int> & height){
    
        int m = height.size();
        int count = 0;
        std::stack<int> stack; // 单调栈：栈底 -> 栈顶： 由小 -> 大
        // 每个元素依次入栈，维持单调栈的严格单调递增结构，不符合时，弹出元素，弹出即结算
        for (int i = 0; i < m; ++i) {
    
            // 维持单调栈的严格单调递增结构，不符合时，弹出元素，弹出即结算
            while (!stack.empty() && height[i] <= height[stack.top()]){
    
                int index = stack.top(); stack.pop();
                int leftIndex = stack.empty() ? -1 : stack.top();// 左侧比[index]小、离index最近的元素位置
                int rightIndex = i;   // 右侧比[index]小、离index最近的元素位置
                int wid = rightIndex - leftIndex - 1;  // 形成的直方图长度
                int hei =  height[index] - std::max(
                        leftIndex == -1 ? 0 : height[leftIndex], height[rightIndex]
                        );
                count += ((wid * (wid+1))/2) * hei; // 公式计算个数
            } 
            stack.push(i);
        }
        // 结算单调栈中最后剩下的元素，弹出元素，弹出即结算
        while (!stack.empty()) {
    
            int index = stack.top(); stack.pop();
            int leftIndex = stack.empty() ? -1 : stack.top();// 左侧比[index]小、离index最近的元素位置
            int rightIndex = m; // 右侧比[index]小、离index最近的元素位置
            int l = rightIndex - leftIndex - 1; // 形成的直方图长度
            // 形成的直方图的有效结算高度 h ：
            int h = height[index] - (leftIndex == -1 ? 0 : height[leftIndex]);
            count += ((l * (l+1))/2) * h; // 公式计算个数
        }

        return count;
    }
public:

    int numSubmat(vector<vector<int>>& mat) {
    
        int m = mat.size(), n = mat[0].size();
        int ans = 0;
        std::vector<int>  height(m);  // 以每一行打底的直方图数组
        for (int i = 0; i < m; ++i) {
    
            // 计算以每一行打底的直方图
            for (int j = 0; j < n; ++j) {
    
                height[j] = mat[i][j] == 0 ? 0 : height[j] + 1;
            }
            // 计算以每一行打底时的全1子矩阵的数量
            int cnt = process(height);
            ans += cnt;
        }
        return ans;
    }
   
};

优化方法是使用数组来实现栈