Medium

题目描述

你有一个 m x n 的二维网格 grid，代表一个箱子，同时你有 n 颗球。箱子的顶部和底部都是开着的。

箱子中的每个单元格都有一个对角线挡板，跨越两个角，可以将球导向左侧或者右侧。

  • 将球导向右侧的挡板跨越左上角和右下角，在网格中用 1 表示。
  • 将球导向左侧的挡板跨越右上角和左下角，在网格中用 -1 表示。

在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 “V” 形图案，或者被挡板导向到箱子的任意一侧边上，就会卡住。

返回一个大小为 n 的数组 answer，其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则为 -1。

示例 1：

输入：grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
输出：[1,-1,-1,-1,-1]
解释：这个示例如图所示。

示例 2：

输入：grid = [[-1]]
输出：[-1]
解释：球被卡在左侧边上。

示例 3：

输入：grid = [[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]]
输出：[0,1,2,3,4,-1]

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • grid[i][j] 是 1 或 -1

解题思路

这是一道经典的网格模拟题，需要模拟球的下落过程。

核心思路：

  1. 对于每颗球，从顶部开始逐行模拟下落过程
  2. 球的移动规律：如果当前位置是 1，球向右下移动；如果是 -1，球向左下移动
  3. 球被卡住的两种情况：
    • 撞到边界：向左移动时已在最左列，或向右移动时已在最右列
    • 形成 “V” 形：当前格子和下一格子的挡板方向相反（如当前是 1 下一个是 -1，或当前是 -1 下一个是 1）

算法步骤：

  1. 遍历每一列，模拟从该列投球
  2. 对于每颗球，从第 0 行开始，逐行计算球的位置
  3. 每次移动前检查是否会被卡住：边界检查和 “V” 形检查
  4. 如果能顺利到达底部，记录最终列位置；否则返回 -1

时间复杂度为 O(m×n)，空间复杂度为 O(1)（不含输出数组）。

代码实现

class Solution {
public:
    vector<int> findBall(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> result(n);
        
        for (int col = 0; col < n; col++) {
            int currentCol = col;
            
            for (int row = 0; row < m; row++) {
                int direction = grid[row][currentCol];
                int nextCol = currentCol + direction;
                
                // 检查边界
                if (nextCol < 0 || nextCol >= n) {
                    currentCol = -1;
                    break;
                }
                
                // 检查是否形成 V 形（被卡住）
                if (grid[row][nextCol] != direction) {
                    currentCol = -1;
                    break;
                }
                
                currentCol = nextCol;
            }
            
            result[col] = currentCol;
        }
        
        return result;
    }
};

class Solution:
    def findBall(self, grid: List[List[int]]) -> List[int]:
        m, n = len(grid), len(grid[0])
        result = []
        
        for col in range(n):
            current_col = col
            
            for row in range(m):
                direction = grid[row][current_col]
                next_col = current_col + direction
                
                # 检查边界
                if next_col < 0 or next_col >= n:
                    current_col = -1
                    break
                
                # 检查是否形成 V 形（被卡住）
                if grid[row][next_col] != direction:
                    current_col = -1
                    break
                
                current_col = next_col
            
            result.append(current_col)
        
        return result

public class Solution {
    public int[] FindBall(int[][] grid) {
        int m = grid.Length, n = grid[0].Length;
        int[] result = new int[n];
        
        for (int col = 0; col < n; col++) {
            int currentCol = col;
            
            for (int row = 0; row < m; row++) {
                int direction = grid[row][currentCol];
                int nextCol = currentCol + direction;
                
                // 检查边界
                if (nextCol < 0 || nextCol >= n) {
                    currentCol = -1;
                    break;
                }
                
                // 检查是否形成 V 形（被卡住）
                if (grid[row][nextCol] != direction) {
                    currentCol = -1;
                    break;
                }
                
                currentCol = nextCol;
            }
            
            result[col] = currentCol;
        }
        
        return result;
    }
}

var findBall = function(grid) {
    const m = grid.length, n = grid[0].length;
    const result = [];
    
    for (let col = 0; col < n; col++) {
        let currentCol = col;
        
        for (let row = 0; row < m; row++) {
            const direction = grid[row][currentCol];
            const nextCol = currentCol + direction;
            
            // 检查边界
            if (nextCol < 0 || nextCol >= n) {
                currentCol = -1;
                break;
            }
            
            // 检查是否形成 V 形（被卡住）
            if (grid[row][nextCol] !== direction) {
                currentCol = -1;
                break;
            }
            
            currentCol = nextCol;
        }
        
        result.push(currentCol);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(m×n)，其中 m 是网格的行数，n 是网格的列数。需要对每一列模拟球的下落过程，每次模拟最多经过 m 行
空间复杂度O(1)，除了输出数组外，只使用了常数级别的额外空间