题目描述
思路解析动画文字版
记住这一句:机器人一挑一列往下拐,机器人二就只能在上排右段和下排左段里挑较大的一块拿走。机器人一要做的,是让这个较大值尽量小。下面我们从头把这张图看明白,再逐列试拐点。
先看整张网格 · 两个机器人的起点和终点：这是我们的舞台,一张 2 行 4 列的网格。上排四个数是 3、1、2、5,下排是 4、2、1、2。两个机器人都从左上角 (0,0) 出发,一路只能向右或向下,最后都要走到右下角 (1,3)。先记住这些点数的位置,尤其上排最右边那个 5 和下排的 4,后面它们是胜负手。
机器人一的路径形状 · 上排走一段就下拐：先看机器人一能走成什么样。因为只能向右或向下,它的路一定是:上排从头往右走到某一列,在那一列往下拐一格,再沿下排走到底。这里拿拐点在第 1 列举个样子,紫色两格就是往下拐的地方,灰色就是它走过并清零的整条路。换个拐点,灰色路径就跟着变。机器人一要挑的,正是这个拐点列。
机器人二只剩两块残料 · 二选一：机器人一走完清零后,轮到机器人二。它眼前只剩两块没被清掉的:绿色是上排拐点右边那一段,橙色是下排拐点左边那一段。关键在于,机器人二也只能向右向下走,一旦下拐就回不到上排,所以这两块它没法都拿,只能挑一块。它当然挑点数大的那块。机器人一要做的,就是选个拐点让这较大的一块尽量小。
试拐点第 0 列 · 机器人一吃掉灰色路径：现在试机器人一在第 0 列往下拐。紫色是它下拐的两格,灰色是它走过并清零的整条路:上排从第 0 列到第 0 列,再下排从第 0 列到第 3 列。这些格子机器人二再来时都是 0 了。接下来看它给机器人二留下了哪两块。
上排残料 · 第 1 列起的一段：先看绿色这块,上排拐点右边、从第 1 列起的一段:1 加 2 加 5,一共 8。机器人二要想拿它,就得在上排一直走到底再下拐。这个数记成 topSuffix,等于 8。
下排残料 · 第 0 列前的一段：拐点就在第 0 列,下排左边没有格子留下,这块是空的,bottomPrefix 等于 0。机器人二在下排这一侧什么也捡不到。
机器人二取较大块 = 8 · 更新最优：机器人二在两块里挑大的:上排后缀 8 和下排前缀 0,较大的是 8,红色标出的就是它实际拿走的那块。也就是说,机器人一要是拐第 0 列,机器人二会拿到 8。把它和之前的最优比一比,目前机器人一能把对手压到最少 8。
试拐点第 1 列 · 机器人一吃掉灰色路径：现在试机器人一在第 1 列往下拐。紫色是它下拐的两格,灰色是它走过并清零的整条路:上排从第 0 列到第 1 列,再下排从第 1 列到第 3 列。这些格子机器人二再来时都是 0 了。接下来看它给机器人二留下了哪两块。
上排残料 · 第 2 列起的一段：先看绿色这块,上排拐点右边、从第 2 列起的一段:2 加 5,一共 7。机器人二要想拿它,就得在上排一直走到底再下拐。这个数记成 topSuffix,等于 7。
下排残料 · 第 1 列前的一段：再看橙色这块,下排拐点左边、前 1 列的一段:4,一共 4。机器人二要想拿它,就得一开始就下拐、沿下排走。这个数记成 bottomPrefix,等于 4。
机器人二取较大块 = 7 · 更新最优：机器人二在两块里挑大的:上排后缀 7 和下排前缀 4,较大的是 7,红色标出的就是它实际拿走的那块。也就是说,机器人一要是拐第 1 列,机器人二会拿到 7。把它和之前的最优比一比,目前机器人一能把对手压到最少 7。
试拐点第 2 列 · 机器人一吃掉灰色路径：现在试机器人一在第 2 列往下拐。紫色是它下拐的两格,灰色是它走过并清零的整条路:上排从第 0 列到第 2 列,再下排从第 2 列到第 3 列。这些格子机器人二再来时都是 0 了。接下来看它给机器人二留下了哪两块。
上排残料 · 第 3 列起的一段：先看绿色这块,上排拐点右边、从第 3 列起的一段:5,一共 5。机器人二要想拿它,就得在上排一直走到底再下拐。这个数记成 topSuffix,等于 5。
下排残料 · 第 2 列前的一段：再看橙色这块,下排拐点左边、前 2 列的一段:4 加 2,一共 6。机器人二要想拿它,就得一开始就下拐、沿下排走。这个数记成 bottomPrefix,等于 6。
机器人二取较大块 = 6 · 更新最优：机器人二在两块里挑大的:上排后缀 5 和下排前缀 6,较大的是 6,红色标出的就是它实际拿走的那块。也就是说,机器人一要是拐第 2 列,机器人二会拿到 6。把它和之前的最优比一比,目前机器人一能把对手压到最少 6。
试拐点第 3 列 · 机器人一吃掉灰色路径：现在试机器人一在第 3 列往下拐。紫色是它下拐的两格,灰色是它走过并清零的整条路:上排从第 0 列到第 3 列,再下排从第 3 列到第 3 列。这些格子机器人二再来时都是 0 了。接下来看它给机器人二留下了哪两块。
上排残料 · 第 4 列起的一段：拐点已经是最后一列了,上排右边没有格子留下,这块是空的,topSuffix 等于 0。机器人二在上排这一侧什么也捡不到。
下排残料 · 第 3 列前的一段：再看橙色这块,下排拐点左边、前 3 列的一段:4 加 2 加 1,一共 7。机器人二要想拿它,就得一开始就下拐、沿下排走。这个数记成 bottomPrefix,等于 7。
机器人二取较大块 = 7 · 更新最优：机器人二在两块里挑大的:上排后缀 0 和下排前缀 7,较大的是 7,红色标出的就是它实际拿走的那块。也就是说,机器人一要是拐第 3 列,机器人二会拿到 7。把它和之前的最优比一比,目前机器人一能把对手压到最少 6。
最优拐点在第 2 列 · 机器人二只拿 6：四种拐法全试完了:拐第 0 列对方拿 8,第 1 列拿 7,第 2 列拿 6,第 3 列拿 7。机器人一当然选让对手最少的那个,也就是拐第 2 列,把机器人二死死压在 6。你看这一拐很妙,机器人一把上排右段压到只剩一个 5,而下排前面 4 加 2 等于 6 更大,所以机器人二只能拿这 6。
回放 · 枚举拐点取 max 的最小值：回顾整个思路:机器人一的路径就是选一列往下拐,拐完给机器人二留下上排右段和下排左段两块残料,机器人二只能二选一拿较大的。我们逐列枚举拐点,每列算出 max(上排后缀, 下排前缀),再取所有列里最小的那个,就是机器人二在双方都最优时拿到的点数,这张图上是 6。真正写代码时,前缀后缀都能一边扫一边增减维护,不用每列重新求和。
边界要点:n 为 1 时对手拿 0;拐点吃掉大数常常最优;上排后缀与下排前缀都严格不含拐点列。
面试重点:路径即选拐点、前缀后缀滚动做到 O(n)、机器人二取 max 且注意 C 加加 用 long long、Java 用 long 防溢出。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def gridGame(self, grid: List[List[int]]) -> int: ans = inf s1, s2 = sum(grid[0]), 0 for j, v in enumerate(grid[0]): s1 -= v ans = min(ans, max(s1, s2)) s2 += grid[1][j] return ans复杂度
- 时间：O(n)，先求一次上排和是 O(n),再从左到右枚举 n 个拐点列,每列只做减一个数、比一次大小、加一个数这几步常数操作,总共随列数 n 线性增长
- 空间：O(1)，只用了 s1、s2、答案这几个变量滚动维护前缀和与后缀和,不额外开数组,占用是常数,不随 n 变化
易错点
面试追问把动画讲成自己的话
追问这题的核心观察是什么?
追问怎么把它做到线性?
追问有哪些容易出错的细节?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
获取单值网格的最小操作数
LeetCode 2033 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题