LeetCode每日一题(2017. Grid Game)

You are given a 0-indexed 2D array grid of size 2 x n, where grid[r][c] represents the number of points at position (r, c) on the matrix. Two robots are playing a game on this matrix.

Both robots initially start at (0, 0) and want to reach (1, n-1). Each robot may only move to the right ((r, c) to (r, c + 1)) or down ((r, c) to (r + 1, c)).

At the start of the game, the first robot moves from (0, 0) to (1, n-1), collecting all the points from the cells on its path. For all cells (r, c) traversed on the path, grid[r][c] is set to 0. Then, the second robot moves from (0, 0) to (1, n-1), collecting the points on its path. Note that their paths may intersect with one another.

The first robot wants to minimize the number of points collected by the second robot. In contrast, the second robot wants to maximize the number of points it collects. If both robots play optimally, return the number of points collected by the second robot.

Example 1:

Input: grid = [[2,5,4],[1,5,1]]
Output: 4

Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 0 + 4 + 0 = 4 points.

Example 2:

Input: grid = [[3,3,1],[8,5,2]]
Output: 4

Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 3 + 1 + 0 = 4 points.
Example 3:

Input: grid = [[1,3,1,15],[1,3,3,1]]
Output: 7

Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 1 + 3 + 3 + 0 = 7 points.

Constraints:

• grid.length == 2
• n == grid[r].length
• 1 <= n <= 5 * 104
• 1 <= grid[r][c] <= 105

---

读题的时候觉得完了完了， 又碰上硬茬了， 因为没思路，所以干脆就发散一下思维， 盯着图看了一会儿，发现其机器人 1 走的路线实际是把整个矩阵分割成了右上和左下两个部分， 当然极端情况下两部分的其中一部分的面积和分值可能为 0， 即如果开始就向下走则左下部分的面积和分值为 0， 如果最后一步往下走则右上部分面积和分值为 0。机器人 2 在走的时候只能在这两部分中选择一部分收集分数。这样问题就转化成了， 遍历查找所有左下和右上两部分的分值当中较大的部分的最小值， 说起来比较拗口， 代码表达出来就是min(max(left_bottom[i], right_top[i]))。这样再转化一步， 假设 first_row_suffix_sum[i]是从 grid[0][i]开始到 grid[0]grid[0].len-1]的 sum, second_row_prefix_sum[i]是从 grid[1][0]到 grid[1][i]的 sum, 这样当机器人 1 从 grid[0][i]向下走走到 grid[1][i]时, 机器人 2 能收集的分数就是 first_row_suffix_sum[i+1]或者 second_row_prefix_sum[i-1]。要注意的是我们开头提到的， 两部分面积和分数为 0 的情况。

---

impl Solution {
    pub fn grid_game(grid: Vec<Vec<i32>>) -> i64 {
        let mut first_row_suffix_sum: Vec<i64> = grid[0]
            .iter()
            .rev()
            .scan(0i64, |s, v| {
                *s += *v as i64;
                Some(*s as i64)
            })
            .collect();
        first_row_suffix_sum.reverse();
        first_row_suffix_sum.push(0);
        let mut second_row_prefix_sum: Vec<i64> = grid[1]
            .iter()
            .scan(0i64, |s, v| {
                *s += *v as i64;
                Some(*s as i64)
            })
            .collect();
        second_row_prefix_sum.insert(0, 0);
        let mut ans = i64::MAX;
        for i in 0..grid[0].len() {
            ans = ans.min(first_row_suffix_sum[i + 1].max(second_row_prefix_sum[i]));
        }
        ans as i64
    }
}