What is the main challenge in the Grid Game problem?

The main challenge is optimizing the paths of two robots in a matrix grid while maximizing the second robot's points, especially when the robots' paths may overlap.

How does the prefix sum technique help solve this problem?

The prefix sum technique allows you to quickly calculate the total points up to any position on the grid, which is crucial for efficiently solving the problem in O(n) time.

What is the optimal strategy for the second robot's path?

The optimal strategy is to use a greedy approach, where the second robot always chooses the path that maximizes its points based on the remaining grid after the first robot's path.

How can I optimize my solution to handle large grid sizes?

By implementing a linear time complexity solution using prefix sums and a greedy strategy, you can solve the problem efficiently even with large grid sizes, up to 50,000 columns.

What happens if the paths of the robots overlap?

When the paths overlap, the first robot collects the points from the shared cells, marking them as 0. The second robot will avoid these cells and choose the next available best path.

#2017

Medium

auto_awesome数组·matrix

LeetCode 题解工作台

网格游戏

给你一个下标从 0 开始的二维数组 grid ，数组大小为 2 x n ，其中 grid[r][c] 表示矩阵中 (r, c) 位置上的点数。现在有两个机器人正在矩阵上参与一场游戏。两个机器人初始位置都是 (0, 0) ，目标位置是 (1, n-1) 。每个机器人只会向右 ( (r, c) 到 …

数组矩阵前缀和

题目描述

给你一个下标从 0 开始的二维数组 grid ，数组大小为 2 x n ，其中 grid[r][c] 表示矩阵中 (r, c) 位置上的点数。现在有两个机器人正在矩阵上参与一场游戏。

两个机器人初始位置都是 (0, 0) ，目标位置是 (1, n-1) 。每个机器人只会向右 ((r, c) 到 (r, c + 1)) 或向下 ((r, c) 到 (r + 1, c)) 。

游戏开始，第一个 机器人从 (0, 0) 移动到 (1, n-1) ，并收集路径上单元格的全部点数。对于路径上所有单元格 (r, c) ，途经后 grid[r][c] 会重置为 0 。然后，第二个 机器人从 (0, 0) 移动到 (1, n-1) ，同样收集路径上单元的全部点数。注意，它们的路径可能会存在相交的部分。

第一个 机器人想要打击竞争对手，使 第二个 机器人收集到的点数 最小化 。与此相对，第二个 机器人想要 最大化 自己收集到的点数。两个机器人都发挥出自己的 最佳水平 的前提下，返回 第二个 机器人收集到的点数。

示例 1：

输入：grid = [[2,5,4],[1,5,1]]
输出：4
解释：第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。
第一个机器人访问过的单元格将会重置为 0 。
第二个机器人将会收集到 0 + 0 + 4 + 0 = 4 个点。

示例 2：

输入：grid = [[3,3,1],[8,5,2]]
输出：4
解释：第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。 
第一个机器人访问过的单元格将会重置为 0 。
第二个机器人将会收集到 0 + 3 + 1 + 0 = 4 个点。

示例 3：

输入：grid = [[1,3,1,15],[1,3,3,1]]
输出：7
解释：第一个机器人的最佳路径如红色所示，第二个机器人的最佳路径如蓝色所示。
第一个机器人访问过的单元格将会重置为 0 。
第二个机器人将会收集到 0 + 1 + 3 + 3 + 0 = 7 个点。

提示：

grid.length == 2
n == grid[r].length
1 <= n <= 5 * 10⁴
1 <= grid[r][c] <= 10⁵

lightbulb

解题思路

方法一：前缀和

我们注意到，如果确定了第一个机器人拐头向下的位置 $j$ ，那么第二个机器人的最优路径也就确定了，第二个机器人的最优路径就是第一行从 $j+1$ 到 $n-1$ 的前缀和，或者第二行从 $0$ 到 $j-1$ 的前缀和，取两者的最大值。

我们先计算第一行的后缀点数和，记为 $s_1$ ，第二行的前缀点数和记为 $s_2$ ，初始时 $s_1 = \sum_{j=0}^{n-1} grid[0][j]$ , $s_2 = 0$ 。

然后我们枚举第一个机器人拐头向下的位置 $j$ ，此时更新 $s_1 = s_1 - grid[0][j]$ , 那么第二个机器人的最优路径和就是 $max(s_1, s_2)$ ，我们取所有 $j$ 对应的 $max(s_1, s_2)$ 的最小值即可。然后更新 $s_2 = s_2 + grid[1][j]$ 。

枚举结束后，返回答案即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。其中 $n$ 是网格的列数。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        ans = inf
        s1, s2 = sum(grid[0]), 0
        for j, v in enumerate(grid[0]):
            s1 -= v
            ans = min(ans, max(s1, s2))
            s2 += grid[1][j]
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Focus on the interaction between the first and second robots' paths to optimize the second robot's collection of points.
question_mark
Examine the trade-offs in choosing paths for the second robot, especially when paths overlap with the first robot's path.
question_mark
The ability to implement efficient algorithms in linear time will be key to solving this problem within the constraints.

warning

常见陷阱

外企场景

error
Forgetting to account for the cells visited by the first robot, which are marked as 0 and affect the second robot's path.
error
Failing to optimize the second robot's path by greedily choosing the best option at each step based on updated matrix values.
error
Not handling the matrix's large size properly within the time limits, leading to inefficient solutions with higher time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Increase the grid size beyond 2 rows and optimize for larger matrixes.
arrow_right_alt
Implementing additional constraints, like diagonal movements or limited robot movement options.
arrow_right_alt
Modifying the game to include dynamic changes in point values during the game, requiring continuous re-evaluation of optimal paths.

help

常见问题

外企场景

继续练习

#2132 用邮票贴满网格图 #1895 最大的幻方 #1878 矩阵中最大的三个菱形和