289. 生命游戏

✨核心逻辑

本题要求使用 原地算法 更新矩阵状态。由于我们修改当前细胞时，需要依赖它周围 8 个邻居在修改前的原始状态，为了防止原地覆盖导致后续细胞计算错误，本题采用了 复合状态标记法：

自定义状态定义（2位状态机）：
- 0：当前死亡，下个状态依然死亡（保持死）
- 1：当前存活，下个状态依然存活（保持活）
- 2：当前存活，下个状态死亡（活 -> 死）
- 3：当前死亡，下个状态存活（死 -> 活）
邻居存活统计技巧：在统计八个方向的邻居时，如果一个邻居是 1 或 2，都要把它算作**“当前存活”**的邻居（因为 2 代表即将死亡，但在当前轮次它依然算作活细胞）。
按规则原地改写：根据统计出的 live 数量，修改当前细胞的状态为对应的复合数字。
二次遍历还原：最后再次遍历整个矩阵，把标记为 2 的改成 0，把标记为 3 的改成 1，得到最终状态。

🔥代码实现（含详细变量注释）

class Solution {
    public void gameOfLife(int[][] board) {
        // 边界检查：如果传入的二维数组为空或者长度为 0，无需处理直接返回
        if (board == null || board.length == 0) {
            return;
        }
        
        // m：记录二维矩阵的总行数
        int m = board.length;
        // n：记录二维矩阵的总列数
        int n = board[0].length;

        // kx、ky：方向数组，分别代表 8 个邻居在行和列上的偏移量
        // 组合起来分别代表：左上、上、右上、左、右、左下、下、右下
        int[] kx = {-1, -1, -1, 0, 0, 1, 1, 1};
        int[] ky = {-1, 0, 1, -1, 1, -1, 0, 1};
        
        // 1. 第一次遍历：计算邻居存活数量，并原地修改为复合状态
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // live：记录当前细胞周围 8 个格子中活细胞的数量
                int live = 0;
                // 遍历 8 个方向
                for (int k = 0; k < 8; k++) {
                    // x1：当前邻居的行索引
                    int x1 = i + kx[k];
                    // y1：当前邻居的列索引
                    int y1 = j + ky[k];
                    
                    // 核心判断：如果邻居坐标在矩阵合法范围内，并且它的状态是 1（原本存活）或 2（原本存活即将死亡）
                    // 只要当前轮次它是活着的，就需要计入 live 总数
                    if (x1 >= 0 && x1 < m && y1 >= 0 && y1 < n && (board[x1][y1] == 1 || board[x1][y1] == 2)) {
                        live++;
                    }
                }
                
                // 根据规则进行状态标记（利用 2 和 3 辅助过渡）
                if (board[i][j] == 0) { // 当前细胞是死细胞
                    // 规则 4：如果死细胞周围正好有 3 个活细胞，该位置死细胞复活
                    if (live == 3) {
                        board[i][j] = 3; // 用 3 标记该格子（死 -> 活）
                    }
                } else { // 当前细胞是活细胞
                    // 规则 1：周围活细胞少于 2 个，该位置活细胞死亡
                    // 规则 3：周围活细胞多于 3 个，该位置活细胞死亡
                    if (live < 2 || live > 3) {
                        board[i][j] = 2; // 用 2 标记该格子（活 -> 死）
                    }
                    // 规则 2：周围有 2 个或 3 个活细胞，维持存活状态（状态为 1，无需改变）
                }
            }
        }
        
        // 2. 第二次遍历：将标记的复合状态还原为真实的 0 和 1
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 如果标记为 2，说明原来活着现在死了，最终状态置为 0
                if (board[i][j] == 2) {
                    board[i][j] = 0;
                }
                // 如果标记为 3，说明原来死了现在活了，最终状态置为 1
                if (board[i][j] == 3) {
                    board[i][j] = 1;
                }
            }
        }
    }
}

⏱️复杂度分析
- 时间复杂度：O(m * n)，其中 m 是矩阵的行数，n 是矩阵的列数。我们需要完整遍历矩阵两次，每次对内部操作都是常数时间（固定检查 8 个邻居），因此总运算次数与矩阵元素总数成正比。
- 空间复杂度：O(1)，我们只是原数组上使用了几个额外的整数变量（如 m, n, kx, ky, live 等）进行辅助计算，没有申请额外的二维数组，满足了题目原地操作的要求。