今日题目

https://leetcode.com/problems/grid-game/description/

解题思路

这是一道特殊情况——网格只有两行。 此外，还需注意网格中所有数字的特性。

由于机器人一旦向下移动就无法回头，这意味着两个机器人各自只有一次机会切换到第二行。

假设机器人一在索引 $k$ 处切换到第二行，会发生什么？

此时，非零的数字只剩两部分：第二行中索引小于 $k$ 的数字，以及第一行中索引大于 $k$ 的数字。

因此，机器人二为了最大化得分，只能二选一：要么拿第一行剩余的数字，要么拿第二行剩余的数字——因为一旦切换到第二行就无法返回第一行。

解法

我们需要计算的是：第一行中索引 $k$ 之后所有数字的总和，以及第二行中索引 $k$ 之前所有数字的总和。

技巧

这里用到一个前缀和技巧来解决此问题：

  1. 第一行中索引 $k$ 之后的数字总和，可以在上一步（索引 $k-1$ 之后的总和）的基础上减去 $grid[k][0]$ 得到。
  2. 第二行中索引 $k$ 之前的数字总和，可以在上一步的基础上加上 $grid[k][1]$ 得到。
  3. 第一行所需的累计和始终递减，而第二行所需的累计和始终递增。

因此，当 $max(sum1, sum2) > presentAns$ 时，可以直接跳出循环——此时 sum2 > sum1 且会持续增大，答案不会再减小了。（其中 sum1 为当前第一行的候选和，sum2 为当前第二行的候选和，presentAns 为迭代到索引 $k$ 时的当前最优答案。）

复杂度

  • 时间复杂度：$O(N)$，N 为网格的列数。

  • 空间复杂度：$O(1)$，仅使用常数个变量。

代码

class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        x,y = sum(grid[0][1:]), 0
        ans = x
        for i in range(1, len(grid[0])):
            x -= grid[0][i]
            y += grid[1][i - 1]

            if ans >= max(x,y):
                ans = max(x,y)
            else:
                return ans
        
        return ans

image.png