Hard

题目描述

农夫有一块 m x n 的矩形土地，可以划分为单元格。每个单元格要么是肥沃的（用 1 表示），要么是贫瘠的（用 0 表示）。网格外的所有单元格都被认为是贫瘠的。

金字塔形地块可以定义为满足以下条件的单元格集合：

  • 集合中的单元格数量必须大于 1，且所有单元格都必须是肥沃的。
  • 金字塔的顶点是金字塔最上面的单元格。金字塔的高度是它覆盖的行数。设 (r, c) 为金字塔的顶点，高度为 h。那么，该地块包含单元格 (i, j)，其中 r <= i <= r + h - 1 且 c - (i - r) <= j <= c + (i - r)。

倒金字塔形地块可以用类似的标准来定义：

  • 集合中的单元格数量必须大于 1，且所有单元格都必须是肥沃的。
  • 倒金字塔的顶点是倒金字塔最下面的单元格。倒金字塔的高度是它覆盖的行数。设 (r, c) 为金字塔的顶点，高度为 h。那么，该地块包含单元格 (i, j)，其中 r - h + 1 <= i <= r 且 c - (r - i) <= j <= c + (r - i)。

给定一个表示农田的 0 索引 m x n 二进制矩阵 grid，返回可以在 grid 中找到的金字塔和倒金字塔地块的总数。

示例 1：

输入：grid = [[0,1,1,0],[1,1,1,1]]
输出：2
解释：2 个可能的金字塔地块分别用蓝色和红色显示。
此网格中没有倒金字塔地块。
因此金字塔和倒金字塔地块的总数为 2 + 0 = 2。

示例 2：

输入：grid = [[1,1,1],[1,1,1]]
输出：2
解释：金字塔地块用蓝色显示，倒金字塔地块用红色显示。
因此地块总数为 1 + 1 = 2。

示例 3：

输入：grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]
输出：13
解释：有 7 个金字塔地块，其中 3 个在第 2 和第 3 个图中显示。
有 6 个倒金字塔地块，其中 2 个在最后一个图中显示。
地块总数为 7 + 6 = 13。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 1000
  • 1 <= m * n <= 10^5
  • grid[i][j] 为 0 或 1

解题思路

这道题要求统计农田中所有可能的正金字塔和倒金字塔数量。关键思路是使用动态规划来记录每个位置作为金字塔顶点时能够构成的最大高度。

核心思路：

  1. 正金字塔处理： 对于位置 (i,j) 作为金字塔顶点，我们需要检查下一行的左右两侧是否都有足够的肥沃土地支撑更大的金字塔。状态转移方程为：dp[i][j] = min(dp[i+1][j-1], dp[i+1][j+1]) + 1

  2. 倒金字塔处理： 类似地，对于倒金字塔，我们从底部开始向上构建，状态转移方程为：dp[i][j] = min(dp[i-1][j-1], dp[i-1][j+1]) + 1

  3. 计数策略： 如果某个位置能构成高度为 h 的金字塔，那么它实际能贡献 h-1 个金字塔（高度从 2 到 h 的所有金字塔）

算法步骤：

  • 首先计算正金字塔：从底部向顶部遍历，对每个肥沃位置计算其作为顶点的最大金字塔高度
  • 然后计算倒金字塔：从顶部向底部遍历，对每个肥沃位置计算其作为顶点的最大倒金字塔高度
  • 最后将所有可能的金字塔数量相加

这种方法的优势在于避免了重复计算，每个位置只需要根据相邻位置的信息就能确定自己的状态。

代码实现

class Solution {
public:
    int countPyramids(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        int result = 0;
        
        // Count regular pyramids (top to bottom)
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dp[i][j] = 1;
                    if (i < m - 1 && j > 0 && j < n - 1) {
                        dp[i][j] = min(dp[i+1][j-1], dp[i+1][j+1]) + 1;
                    }
                    result += dp[i][j] - 1;
                }
            }
        }
        
        // Reset dp array for inverse pyramids
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = 0;
            }
        }
        
        // Count inverse pyramids (bottom to top)
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dp[i][j] = 1;
                    if (i > 0 && j > 0 && j < n - 1) {
                        dp[i][j] = min(dp[i-1][j-1], dp[i-1][j+1]) + 1;
                    }
                    result += dp[i][j] - 1;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def countPyramids(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[0] * n for _ in range(m)]
        result = 0
        
        # Count regular pyramids (top to bottom)
        for i in range(m - 1, -1, -1):
            for j in range(n):
                if grid[i][j] == 1:
                    dp[i][j] = 1
                    if i < m - 1 and 0 < j < n - 1:
                        dp[i][j] = min(dp[i+1][j-1], dp[i+1][j+1]) + 1
                    result += dp[i][j] - 1
        
        # Reset dp array for inverse pyramids
        dp = [[0] * n for _ in range(m)]
        
        # Count inverse pyramids (bottom to top)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    dp[i][j] = 1
                    if i > 0 and 0 < j < n - 1:
                        dp[i][j] = min(dp[i-1][j-1], dp[i-1][j+1]) + 1
                    result += dp[i][j] - 1
        
        return result

public class Solution {
    public int CountPyramids(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int[,] dp = new int[m, n];
        int result = 0;
        
        // Count regular pyramids (top to bottom)
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dp[i, j] = 1;
                    if (i < m - 1 && j > 0 && j < n - 1) {
                        dp[i, j] = Math.Min(dp[i+1, j-1], dp[i+1, j+1]) + 1;
                    }
                    result += dp[i, j] - 1;
                }
            }
        }
        
        // Reset dp array for inverse pyramids
        dp = new int[m, n];
        
        // Count inverse pyramids (bottom to top)
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    dp[i, j] = 1;
                    if (i > 0 && j > 0 && j < n - 1) {
                        dp[i, j] = Math.Min(dp[i-1, j-1], dp[i-1, j+1]) + 1;
                    }
                    result += dp[i, j] - 1;
                }
            }
        }
        
        return result;
    }
}

/**
 * @param {number[][]} grid
 * @return {number}
 */
var countPyramids = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    
    function countPyramidsDirection(grid, reverse = false) {
        const dp = Array(m).fill().map(() => Array(n).fill(0));
        let count = 0;
        
        const startRow = reverse ? m - 1 : 0;
        const endRow = reverse ? -1 : m;
        const step = reverse ? -1 : 1;
        
        // Initialize first row
        for (let j = 0; j < n; j++) {
            dp[startRow][j] = grid[startRow][j];
        }
        
        // Fill dp table
        for (let i = startRow + step; i !== endRow; i += step) {
            for (let j = 0; j < n; j++) {
                if (grid[i][j] === 1) {
                    if (j > 0 && j < n - 1) {
                        dp[i][j] = Math.min(dp[i - step][j - 1], dp[i - step][j], dp[i - step][j + 1]) + 1;
                    } else {
                        dp[i][j] = 1;
                    }
                    count += Math.max(0, dp[i][j] - 1);
                }
            }
        }
        
        return count;
    }
    
    return countPyramidsDirection(grid, false) + countPyramidsDirection(grid, true);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(m × n)
空间复杂度O(m × n)

时间复杂度：需要遍历整个网格两次（正金字塔和倒金字塔各一次），每次遍历的时间复杂度为 O(m × n)。

空间复杂度：使用了 dp 数组来存储每个位置作为金字塔顶点时的最大高度，空间复杂度为 O(m × n)。

相关题目