前缀和思维求金字塔个数

解题思路：

利用前缀和的思维，创建一个存储按行连续的 “1” 的个数的矩阵
按分别按 “右下”和 “右上” 方向走步，代表着金字塔的层次增加
符合构成金字塔的条件是当前金字塔的最右方拥有至少拥有 2*层数-1 个连续的 “1”

复杂度分析：

时间复杂度：三层循环 $O_{(m^2n)}$
空间复杂度：使用前缀和数组 $O_{(m\times n)}$ ，利用原数组grid创建前缀和数组 $O_{(1)}$

代码：

class Solution {
public:
    int countPyramids(vector<vector<int>>& grid) {
        int len_g = grid.size(), len_v = grid[0].size();
        int num[len_g][len_v];
        
        for(int i = 0; i < len_g; i++){
            int t = 0;
            for(int j = 0; j < len_v; j++){
                if(grid[i][j]) num[i][j] = ++t;
                else num[i][j] = t = 0;
            }
        }
        
        int ans = 0;
        for(int i = 0; i < len_g; i++){
            for(int  j = 0; j < len_v; j++){
                if(num[i][j]){
                    int h = 2, a = i+1, b = j+1;
                    while(a < len_g && b < len_v && h*2-1 <= num[a][b]){
                        ans++, a++, b++, h++;
                    }
                    
                    h = 2, a = i-1, b = j+1;
                    while(~a && b < len_v && h*2-1 <= num[a][b]) {
                        ans++, a--, b++, h++;
                    }
                }
            }
        }
        return ans;
    }
};