网格游戏

难度: Medium

给你一个下标从 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⁵

Submission

运行时间: 117 ms

内存: 27.1 MB

class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        n=len(grid[0])
        # pre_sum=[0]*n
        # suf_sum=[0]*n
        # for j in range(n):
        #     pre_sum[j]=pre_sum[j-1 if j-1>=0 else 0]+grid[1][j]
        # for j in range(n-1,-1,-1):
        #     suf_sum[j]=suf_sum[j+1 if j+1<=n-1 else n-1]+grid[0][j]
        ans=inf
        s=0
        s2=sum(grid[0])
        for i in range(n):
            s2-=grid[0][i]
            ans=min(ans,max(s,s2))
            s+=grid[1][i]
        return ans

Explain

题解采用了前缀和和后缀和的思想来解决问题。首先，定义两个变量 s 和 s2，其中 s 为第一行的前缀和，s2 为第二行的后缀和。s2 初始值为第一行的总和。迭代过程中，每次循环减去 grid[0][i] 更新 s2 的值，然后将 grid[1][i] 加到 s 上。每次循环计算 max(s, s2) 作为两个机器人在当前点交汇时，第二个机器人能取得的最大点数。使用变量 ans 来记录迭代过程中的最小值 max(s, s2)，最终返回这个最小值，即第二个机器人在最优策略下能收集到的最大点数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        n = len(grid[0])  # 获取列数
        ans = float('inf')  # 初始化ans为无穷大
        s = 0  # 初始化第二行的前缀和
        s2 = sum(grid[0])  # 初始化第一行的总和
        for i in range(n):
            s2 -= grid[0][i]  # 更新第一行剩余的后缀和
            ans = min(ans, max(s, s2))  # 计算在第i列交汇时，第二机器人的最大可能得分，并更新最小值
            s += grid[1][i]  # 更新第二行的前缀和
        return ans  # 返回第二个机器人在最优策略下能得到的最大点数

Explore

在本题中，前缀和和后缀和被用来计算两个机器人在任意列交汇时可能的得分差异。前缀和 `s` 表示从最左侧开始到当前列的第二行的累积得分，而后缀和 `s2` 表示从当前列开始到最右侧的第一行的累积得分。通过这种方式，我们可以快速计算出在任一点分割网格后，两条路径的得分。第一个机器人总是走第一行，然后向下移动到第二行，因此其路径的剩余得分可以通过后缀和快速得到；第二个机器人则首先在第二行移动，其得分通过前缀和计算。这样，我们就可以迅速得到在每一列交汇点两个机器人各自的得分情况。

在迭代过程中更新第一行的后缀和 `s2` 和第二行的前缀和 `s` 是为了计算在当前列交汇时两个机器人的得分情况。这种更新方式允许我们在遍历网格时动态地调整得分，以反映由于机器人移动导致的得分变化。第一行的后缀和 `s2` 减去当前列的值，反映了第一个机器人从当前列到最右侧的潜在最高得分；而第二行的前缀和 `s` 加上当前列的值，则表示第二个机器人从最左侧到当前列的累计得分。这样的动态更新确保了在每一步都能准确计算出两个机器人的得分，以找到最优的交汇点。

使用 `max(s, s2)` 来计算确实有助于确保第一个机器人的选择尽可能减少第二个机器人的得分。此逻辑基于最坏情况考虑，即无论第一个机器人如何选择路径，我们都假设第二个机器人能够得到 `max(s, s2)` 这个得分。这种方法的目的是找到一个点，使得在该点交汇时第二个机器人的得分（考虑最坏情况下的最大得分）尽可能最小。因此，算法不断更新并寻找可以使得 `max(s, s2)` 值最小的交汇点，从而确保第一个机器人的路径选择对第二个机器人的得分影响最小，达到双方相对公平的结果。