问题1: 给你一个整数 n，一个二维整数数组 restrictions，以及一个长度为 n - 1 ...
Erstellt am: 3. Januar 2026
Beantwortet mit GPT-5.2 Thinking von Chat01
Frage
问题1:
给你一个整数 n，一个二维整数数组 restrictions，以及一个长度为 n - 1 的整数数组 diff。你的任务是构造一个长度为 n 的序列，记为 a[0], a[1], ..., a[n - 1]，使其满足以下条件：
a[0] 为 0。
序列中的所有元素都是 非负整数。
对于每个下标 i (0 <= i <= n - 2)，满足 abs(a[i] - a[i + 1]) <= diff[i]。
对于每个 restrictions[i] = [idx, maxVal]，序列中位置 idx 的值不得超过 maxVal（即 a[idx] <= maxVal）。
你的目标是在满足上述所有条件的情况下，构造一个合法的序列并 最大化 该序列中的 最大 值。
返回一个整数，表示最优序列中出现的 最大 值。
示例 1:
输入: n = 10, restrictions = [[3,1],[8,1]], diff = [2,2,3,1,4,5,1,1,2]
输出: 6
解释:
序列 a = [0, 2, 4, 1, 2, 6, 2, 1, 1, 3] 满足给定的限制条件（a[3] <= 1 且 a[8] <= 1）。
序列中的最大值为 6。
示例 2:
输入: n = 8, restrictions = [[3,2]], diff = [3,5,2,4,2,3,1]
输出: 12
解释:
序列 a = [0, 3, 3, 2, 6, 8, 11, 12] 满足给定的限制条件（a[3] <= 2）。
序列中的最大值为 12。
提示:
2 <= n <= 10^5
1 <= restrictions.length <= n - 1
restrictions[i].length == 2
restrictions[i] = [idx, maxVal]
1 <= idx < n
1 <= maxVal <= 10^6
diff.length == n - 1
1 <= diff[i] <= 10
restrictions[i][0] 的值是唯一的。
class Solution {
public int findMaxVal(int n, int[][] restrictions, int[] diff) {
}
}
问题2:
给你一个大小为 n 的字符串数组 grid，其中每个字符串 grid[i] 的长度为 m。字符 grid[i][j] 是以下符号之一：
'.'：该单元格可用。
'#'：该单元格被阻塞。
你想计算攀爬 grid 的不同路径数量。每条路径必须从最后一行（第 n - 1 行）的任何一个格子开始，并在第一行（第 0 行）结束。
但是，路径受到以下限制：
你只能从一个可用单元格移动到 另一个 可用单元格。
每次移动的 欧几里得距离至多为 d，其中 d 是给定的整数参数。两个单元格 (r1, c1) 和 (r2, c2) 之间的欧几里得距离为 sqrt((r1 - r2)2 + (c1 - c2)2)。
每次移动要么留在同一行，要么移动到正上方的一行（从第 r 行到第 r - 1 行）。
你不能连续两次移动都留在同一行。如果你在一次移动中留在同一行（且该移动不是最后一次移动），你的下一次移动必须进入上一行。
返回一个整数，表示此类路径的数量。由于答案可能很大，请将其对109 + 7取余后返回。
示例 1:
输入: grid = ["..","#."], d = 1
输出: 2
解释:
我们按顺序标记路径中访问的单元格，从 1 开始。两条路径分别是：
.2
#1
32
#1
我们可以从单元格 (1, 1) 移动到单元格 (0, 1)，因为欧几里得距离为 sqrt((1 - 0)2 + (1 - 1)2) = sqrt(1) <= d。
但是，我们不能从单元格 (1, 1) 移动到单元格 (0, 0)，因为欧几里得距离为 sqrt((1 - 0)2 + (1 - 0)2) = sqrt(2) > d。
示例 2:
输入: grid = ["..","#."], d = 2
输出: 4
解释:
示例 1 中的两条路径也符合条件。另外两条路径是：
#1
23
#1
注意，我们可以从 (1, 1) 移动到 (0, 0)，因为欧几里得距离 sqrt(2) <= d。
示例 3:
输入: grid = ["#"], d = 750
输出: 0
解释:
我们无法选择任何单元格作为起始单元格。因此，不存在路径。
示例 4:
输入: grid = [".."], d = 1
输出: 4
解释:
可能的路径为：
.1
1.
12
21
提示:
1 <= n == grid.length <= 750
1 <= m == grid[i].length <= 750
grid[i][j] 为 '.' 或 '#'。
1 <= d <= 750
class Solution {
public int numberOfRoutes(String[] grid, int d) {
}
} 解决这两个问题，通过所有例子，并且不能超时
Gedanke
Antwort
下面给出两个题都可过所有样例且不会超时的做法与 Java 代码（两题是两个独立的 Solution，提交时分别提交对应那题即可）。
问题 1：最大化序列最大值
核心思路（O(n)）
把每个位置的“允许最大值”当作上界 cap[i]（无约束则为 INF，且 cap[0]=0）。
相邻约束 |a[i]-a[i+1]|<=diff[i] 等价于上界传播：
- 从左到右：
a[i] <= a[i-1] + diff[i-1] - 从右到左：
a[i] <= a[i+1] + diff[i]
做两遍松弛后得到每个位置的最大可取上界 upper[i]，那么取 a[i]=upper[i] 本身就是合法序列，并且其最大值就是答案。
时间 O(n)，空间 O(n)。
javaimport java.util.*; class Solution { public int findMaxVal(int n, int[][] restrictions, int[] diff) { final int INF = 1_000_000_000; int[] cap = new int[n]; Arrays.fill(cap, INF); cap[0] = 0; for (int[] r : restrictions) { cap[r[0]] = r[1]; } int[] upper = new int[n]; upper[0] = 0; // Left -> Right: upper[i] = min(cap[i], upper[i-1] + diff[i-1]) for (int i = 1; i < n; i++) { int v = upper[i - 1] + diff[i - 1]; upper[i] = Math.min(cap[i], v); } // Right -> Left: upper[i] = min(upper[i], upper[i+1] + diff[i]) for (int i = n - 2; i >= 0; i--) { int v = upper[i + 1] + diff[i]; if (v < upper[i]) upper[i] = v; } int ans = 0; for (int i = 0; i < n; i++) ans = Math.max(ans, upper[i]); return ans; } }
问题 2：攀爬路径计数（带“不能连续同层移动”）
状态设计（O(n*m)）
对每个格子 (r,c) 维护两种状态：
U[r][c]：到达(r,c)时，上一步不是同层移动（可以选择同层或上移）S[r][c]：到达(r,c)时，上一步是同层移动（下一步若还没结束则必须上移）
转移：
- 上移：从
r到r-1，水平偏移满足
(dr=1) => 1 + dx^2 <= d^2 => |dx| <= floor(sqrt(d^2-1)) = du
所以：
U[r-1][c] += sum_{k in [c-du, c+du]} (U[r][k] + S[r][k])
- 同层移动：从
U[r]走到同一行S[r]，水平偏移|dx|<=d，且必须是另一个格子（排除自身）：
S[r][c] += sum_{k in [c-d, c+d]} U[r][k] - U[r][c]
两种“区间求和”都用前缀和做到每行 O(m)，总 O(nm)（≤ 750750 很稳）。
起点：最后一行任意 '.' 作为开始，相当于 U[last][c]=1。
答案：第一行所有 '.' 的 U[0][c]+S[0][c] 之和（因为可以在第一行结束，也可以最后一步做一次同层移动后结束）。
javaimport java.util.*; class Solution { private static final int MOD = 1_000_000_007; public int numberOfRoutes(String[] grid, int d) { int n = grid.length; int m = grid[0].length(); // du = floor(sqrt(d^2 - 1)) for moves to row-1 long sq = 1L * d * d - 1; int du = (sq <= 0) ? 0 : (int) Math.floor(Math.sqrt(sq)); int[] Ubelow = new int[m]; int[] Sbelow = new int[m]; for (int r = n - 1; r >= 0; r--) { int[] Ucur = new int[m]; int[] Scur = new int[m]; String row = grid[r]; if (r == n - 1) { // start positions for (int c = 0; c < m; c++) { Ucur[c] = (row.charAt(c) == '.') ? 1 : 0; } } else { // compute Ucur from row r+1 (Ubelow, Sbelow) using interval sums with radius du int[] T = new int[m]; for (int c = 0; c < m; c++) { int v = Ubelow[c] + Sbelow[c]; if (v >= MOD) v -= MOD; T[c] = v; } int[] pref = buildPrefix(T); for (int c = 0; c < m; c++) { if (row.charAt(c) == '#') { Ucur[c] = 0; } else { Ucur[c] = intervalSum(pref, c - du, c + du, m); } } } // compute Scur from Ucur within same row using radius d, excluding self int[] prefU = buildPrefix(Ucur); for (int c = 0; c < m; c++) { if (row.charAt(c) == '#') { Scur[c] = 0; } else { int sum = intervalSum(prefU, c - d, c + d, m); int val = sum - Ucur[c]; if (val < 0) val += MOD; Scur[c] = val; } } Ubelow = Ucur; Sbelow = Scur; } // now Ubelow/Sbelow correspond to row 0 long ans = 0; for (int c = 0; c < grid[0].length(); c++) { if (grid[0].charAt(c) == '.') { ans += Ubelow[c]; ans += Sbelow[c]; ans %= MOD; } } return (int) ans; } private int[] buildPrefix(int[] arr) { int m = arr.length; int[] pref = new int[m + 1]; for (int i = 0; i < m; i++) { int v = pref[i] + arr[i]; if (v >= MOD) v -= MOD; pref[i + 1] = v; } return pref; } // inclusive [l, r] private int intervalSum(int[] pref, int l, int r, int m) { if (l < 0) l = 0; if (r >= m) r = m - 1; if (l > r) return 0; int res = pref[r + 1] - pref[l]; if (res < 0) res += MOD; return res; } }
如果你希望我把两题代码合并成一个文件（避免两个 Solution 类名冲突），我也可以给一个“统一类名 + 两个方法”的版本。