Medium

题目描述

给你一个下标从 0 开始、大小为 2 x n 的二维数组 grid，其中 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

示例 3：

输入：grid = [[1,3,1,15],[1,3,3,1]]
输出：7

约束条件：

  • grid.length == 2
  • n == grid[r].length
  • 1 <= n <= 5 * 10^4
  • 1 <= grid[r][c] <= 10^5

解题思路

解题思路

这是一个博弈论问题。关键观察是：第一个机器人的路径必须在某个位置从第一行转到第二行，这个转折点决定了第二个机器人能收集到的最大点数。

核心思路：

  1. 路径分析：第一个机器人必须在某个位置 i 从 (0, i) 移动到 (1, i)，然后继续在第二行移动到终点。

  2. 剩余区域：第一个机器人走过后，剩余的区域形成两个矩形：

    • 上方矩形：第一行中位置 i+1 到 n-1 的区域
    • 下方矩形：第二行中位置 0 到 i-1 的区域

  3. 最优策略：第二个机器人会选择这两个区域中点数更多的那个，因此第二个机器人的得分是这两个区域点数的最大值。

  4. 第一个机器人的策略：为了最小化第二个机器人的得分，第一个机器人需要选择转折点 i，使得两个剩余区域的最大值尽可能小。

算法步骤：

  1. 计算第一行和第二行的前缀和
  2. 对每个可能的转折点 i，计算两个剩余区域的点数
  3. 找到使第二个机器人最小得分的转折点

推荐解法：前缀和 + 枚举转折点

时间复杂度O(n)，空间复杂度O(1)，是最优解法。

代码实现

class Solution {
public:
    long long gridGame(vector<vector<int>>& grid) {
        int n = grid[0].size();
        long long topSum = 0, bottomSum = 0;
        
        // 计算第一行总和
        for (int i = 0; i < n; i++) {
            topSum += grid[0][i];
        }
        
        long long result = LLONG_MAX;
        
        // 枚举第一个机器人的转折点
        for (int i = 0; i < n; i++) {
            topSum -= grid[0][i];  // 第一行剩余部分
            
            // 第二个机器人的最优选择是两个区域的最大值
            long long secondRobotScore = max(topSum, bottomSum);
            result = min(result, secondRobotScore);
            
            bottomSum += grid[1][i];  // 第二行已访问部分
        }
        
        return result;
    }
};

class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        n = len(grid[0])
        top_sum = sum(grid[0])
        bottom_sum = 0
        result = float('inf')
        
        # 枚举第一个机器人的转折点
        for i in range(n):
            top_sum -= grid[0][i]  # 第一行剩余部分
            
            # 第二个机器人的最优选择是两个区域的最大值
            second_robot_score = max(top_sum, bottom_sum)
            result = min(result, second_robot_score)
            
            bottom_sum += grid[1][i]  # 第二行已访问部分
        
        return result

public class Solution {
    public long GridGame(int[][] grid) {
        int n = grid[0].Length;
        long topSum = 0, bottomSum = 0;
        
        // 计算第一行总和
        for (int i = 0; i < n; i++) {
            topSum += grid[0][i];
        }
        
        long result = long.MaxValue;
        
        // 枚举第一个机器人的转折点
        for (int i = 0; i < n; i++) {
            topSum -= grid[0][i];  // 第一行剩余部分
            
            // 第二个机器人的最优选择是两个区域的最大值
            long secondRobotScore = Math.Max(topSum, bottomSum);
            result = Math.Min(result, secondRobotScore);
            
            bottomSum += grid[1][i];  // 第二行已访问部分
        }
        
        return result;
    }
}

var gridGame = function(grid) {
    const n = grid[0].length;
    let topSum = grid[0].reduce((sum, val) => sum + val, 0);
    let bottomSum = 0;
    let result = Infinity;
    
    // 枚举第一个机器人的转折点
    for (let i = 0; i < n; i++) {
        topSum -= grid[0][i];  // 第一行剩余部分
        
        // 第二个机器人的最优选择是两个区域的最大值
        const secondRobotScore = Math.max(topSum, bottomSum);
        result = Math.min(result, secondRobotScore);
        
        bottomSum += grid[1][i];  // 第二行已访问部分
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历一次网格计算前缀和，然后枚举n个转折点
空间复杂度O(1)只使用常数个变量存储前缀和

相关题目