题目

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

1 <= grid[r][c] <= 105

解题思路分析

1、前缀和+贪心；时间复杂度O(n)，空间复杂度O(n)

func gridGame(grid [][]int) int64 {
   n := len(grid[0])
   a := make([]int, n) // 前缀和：上边：从右到左
   b := make([]int, n) // 前缀和：下边，从左到右
   for i := n - 1; i > 0; i-- {
      a[i-1] = a[i] + grid[0][i]
   }
   for i := 0; i < n-1; i++ {
      b[i+1] = b[i] + grid[1][i]
   }
   res := math.MaxInt64
   // 当第一个机器人选择第i点往下走的时候
   // 第一个机器人不需要选择最大值，只需要考虑让第二个机器人选择最小
   for i := 0; i < n; i++ {
      // 第二个机器人只有2个选择，选其中最大的
      // 1、从第0个点往下走，拿到b[i]值
      // 2、一直往右走，拿到a[i]值
      res = min(res, max(a[i], b[i]))
   }
   return int64(res)
}

func min(a, b int) int {
   if a > b {
      return b
   }
   return a
}

func max(a, b int) int {
   if a > b {
      return a
   }
   return b
}

总结

Medium题目，前缀和题目；采用贪心思路