球会落何处

用一个大小为 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]
解释：示例如图：
b0 球开始放在第 0 列上，最终从箱子底部第 1 列掉出。
b1 球开始放在第 1 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。
b2 球开始放在第 2 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b3 球开始放在第 3 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b4 球开始放在第 4 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。

示例 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

/*
题目思路：
使用Java Stream API来实现相同的逻辑。我们通过Stream流的方式来遍历和处理每个球的位置变化，并最终返回每个球的掉落结果。
*/
import java.util.stream.IntStream;

public class Solution {
    public int[] findBall(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        return IntStream.range(0, n).map(i -> {
            int col = i;
            for (int row = 0; row < m; row++) {
                int nextCol = col + grid[row][col];
                if (nextCol < 0 || nextCol >= n || grid[row][nextCol] != grid[row][col]) {
                    return -1;
                }
                col = nextCol;
            }
            return col;
        }).toArray();
    }
}

The solution simulates the path of each ball from the top of the grid to the bottom or until it gets stuck. For each ball, it starts at the top of a column and moves downwards. At each step, based on the direction of the current grid cell (either 1 for right or -1 for left), it tries to move to the adjacent column in that direction. If the ball attempts to move outside the grid bounds or into a cell whose direction forms a 'V' shape with the current cell's direction (i.e., the directions are opposite), the ball gets stuck, and the loop for that ball breaks. If a ball reaches the bottom without getting stuck, its final column position is recorded in the answer array. Otherwise, the position remains -1 indicating the ball got stuck.

O(m * n)

O(n)