LeetCode 1964 障碍物赛道逐位最长有效长度非严格 LIS 的三种 DP 解法与二分边界详解【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以仓库文档 articles/find-the-longest-valid-obstacle-course-at-each-position.md 为核心系统讲解 LeetCode 1964 Find the Longest Valid Obstacle Course at Each Position 的完整求解思路从 O(n²) 的自顶向下记忆化 DP到 O(n log n) 的二分搜索优化版再到空间更省的动态数组版。读完你既能掌握每个位置结尾的最长非严格递增子序列的三种标准解法也能理清 upper bound 与 lower bound 在子序列问题中的选择边界并对照本仓库 经典 LIS 题解 与多语言实现如 C 实现、Kotlin 实现做到理论与代码双重落地。问题定义与前置知识本题要求给定整数数组obstacles对每个位置i求出以obstacles[i]结尾的最长有效赛道长度。所谓有效赛道是指从前往后选出的一段下标递增的子序列且相邻两个障碍高度满足非严格递增即允许相等obstacles[j] obstacles[k]。由于每个位置自身必然构成长度为 1 的赛道答案数组的最小值恒为 1。动手解题前需要具备以下基础动态规划Dynamic Programming通过记录状态来构建最优子序列本题的自顶向下版本即依赖记忆化搜索最长递增子序列LIS本题是经典 LIS 的变体将严格递增放宽为非严格递增仓库中的 articles/longest-increasing-subsequence.md 及其 Python 实现 是理解本题的最佳前置材料二分搜索Binary Search用于把 LIS 类问题从 O(n²) 优化到 O(n log n)Upper Bound 与 Lower Bound 的区别何时使用第一个大于目标的位置、何时使用第一个大于等于目标的位置是子序列类问题能否写对的关键。1. 动态规划自顶向下Top-Down直觉对于每个位置我们希望求出以该位置结尾、且元素间满足后一个不小于前一个的最长递增子序列。这是经典 LIS 的变体。可以使用记忆化搜索对每个下标以及前一个被选中的元素我们有两种选择——如果当前元素合法没有前驱或当前元素小于等于前驱就把它纳入序列否则跳过它。算法步骤创建二维记忆化表dp[i][prev]表示考虑下标0..i的元素、且最后选中的元素下标为prev时能构成的最长有效序列长度定义递归函数dfs(i, prev)基准情形若i 0返回0若该状态已计算过直接返回缓存值选择一跳过当前元素递归dfs(i - 1, prev)选择二若合法没有前驱prev n或obstacles[prev] obstacles[i]纳入当前元素并递归dfs(i - 1, i)取两者较大值并缓存调用dfs(n - 1, n)填充整张表然后从缓存值构造结果数组。from typing import List class Solution: def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) - List[int]: n len(obstacles) dp [[-1] * (n 1) for _ in range(n)] def dfs(i, prev): if i 0: return 0 if dp[i][prev] ! -1: return dp[i][prev] res dfs(i - 1, prev) if prev n or obstacles[prev] obstacles[i]: res max(res, 1 dfs(i - 1, i)) dp[i][prev] res return res dfs(n - 1, n) return [1] [1 dp[i - 1][i] for i in range(1, n)]import java.util.Arrays; public class Solution { private int[][] dp; public int[] longestObstacleCourseAtEachPosition(int[] obstacles) { int n obstacles.length; this.dp new int[n][n 1]; for (int[] row : dp) { Arrays.fill(row, -1); } dfs(n - 1, n, obstacles); int[] res new int[n]; res[0] 1; for (int i 1; i n; i) { res[i] 1 dp[i - 1][i]; } return res; } private int dfs(int i, int prev, int[] obstacles) { if (i 0) { return 0; } if (dp[i][prev] ! -1) { return dp[i][prev]; } int res dfs(i - 1, prev, obstacles); if (prev obstacles.length || obstacles[prev] obstacles[i]) { res Math.max(res, 1 dfs(i - 1, i, obstacles)); } return dp[i][prev] res; } }#include vector using namespace std; class Solution { public: vectorvectorint dp; vectorint longestObstacleCourseAtEachPosition(vectorint obstacles) { int n obstacles.size(); this-dp vectorvectorint(n, vectorint(n 1, -1)); dfs(n - 1, n, obstacles); vectorint res(n, 1); for (int i 1; i n; i) { res[i] 1 dp[i - 1][i]; } return res; } private: int dfs(int i, int prev, vectorint obstacles) { if (i 0) { return 0; } if (dp[i][prev] ! -1) { return dp[i][prev]; } int res dfs(i - 1, prev, obstacles); if (prev obstacles.size() || obstacles[prev] obstacles[i]) { res max(res, 1 dfs(i - 1, i, obstacles)); } return dp[i][prev] res; } };class Solution { /** * param {number[]} obstacles * return {number[]} */ longestObstacleCourseAtEachPosition(obstacles) { const n obstacles.length; const dp Array.from({ length: n }, () new Array(n 1).fill(-1)); const dfs (i, prev) { if (i 0) { return 0; } if (dp[i][prev] ! -1) { return dp[i][prev]; } let res dfs(i - 1, prev); if (prev n || obstacles[prev] obstacles[i]) { res Math.max(res, 1 dfs(i - 1, i)); } dp[i][prev] res; return res; }; dfs(n - 1, n); const res new Array(n).fill(1); for (let i 1; i n; i) { res[i] 1 dp[i - 1][i]; } return res; } }public class Solution { private int[][] dp; public int[] LongestObstacleCourseAtEachPosition(int[] obstacles) { int n obstacles.Length; dp new int[n][]; for (int i 0; i n; i) { dp[i] new int[n 1]; Array.Fill(dp[i], -1); } Dfs(n - 1, n, obstacles); int[] res new int[n]; res[0] 1; for (int i 1; i n; i) { res[i] 1 dp[i - 1][i]; } return res; } private int Dfs(int i, int prev, int[] obstacles) { if (i 0) return 0; if (dp[i][prev] ! -1) return dp[i][prev]; int res Dfs(i - 1, prev, obstacles); if (prev obstacles.Length || obstacles[prev] obstacles[i]) { res Math.Max(res, 1 Dfs(i - 1, i, obstacles)); } return dp[i][prev] res; } }func longestObstacleCourseAtEachPosition(obstacles []int) []int { n : len(obstacles) dp : make([][]int, n) for i : range dp { dp[i] make([]int, n1) for j : range dp[i] { dp[i][j] -1 } } var dfs func(i, prev int) int dfs func(i, prev int) int { if i 0 { return 0 } if dp[i][prev] ! -1 { return dp[i][prev] } res : dfs(i-1, prev) if prev n || obstacles[prev] obstacles[i] { res max(res, 1dfs(i-1, i)) } dp[i][prev] res return res } dfs(n-1, n) res : make([]int, n) res[0] 1 for i : 1; i n; i { res[i] 1 dp[i-1][i] } return res } func max(a, b int) int { if a b { return a } return b }class Solution { private lateinit var dp: ArrayIntArray fun longestObstacleCourseAtEachPosition(obstacles: IntArray): IntArray { val n obstacles.size dp Array(n) { IntArray(n 1) { -1 } } dfs(n - 1, n, obstacles) val res IntArray(n) { 1 } for (i in 1 until n) { res[i] 1 dp[i - 1][i] } return res } private fun dfs(i: Int, prev: Int, obstacles: IntArray): Int { if (i 0) return 0 if (dp[i][prev] ! -1) return dp[i][prev] var res dfs(i - 1, prev, obstacles) if (prev obstacles.size || obstacles[prev] obstacles[i]) { res maxOf(res, 1 dfs(i - 1, i, obstacles)) } dp[i][prev] res return res } }class Solution { private var dp: [[Int]] [] func longestObstacleCourseAtEachPosition(_ obstacles: [Int]) - [Int] { let n obstacles.count dp Array(repeating: Array(repeating: -1, count: n 1), count: n) dfs(n - 1, n, obstacles) var res Array(repeating: 1, count: n) for i in 1..n { res[i] 1 dp[i - 1][i] } return res } private func dfs(_ i: Int, _ prev: Int, _ obstacles: [Int]) - Int { if i 0 { return 0 } if dp[i][prev] ! -1 { return dp[i][prev] } var res dfs(i - 1, prev, obstacles) if prev obstacles.count || obstacles[prev] obstacles[i] { res max(res, 1 dfs(i - 1, i, obstacles)) } dp[i][prev] res return res } }impl Solution { pub fn longest_obstacle_course_at_each_position(obstacles: Veci32) - Veci32 { let n obstacles.len(); let mut dp vec![vec![-1i32; n 1]; n]; fn dfs(i: i32, prev: usize, obstacles: [i32], dp: mut VecVeci32) - i32 { if i 0 { return 0; } let ui i as usize; if dp[ui][prev] ! -1 { return dp[ui][prev]; } let mut res dfs(i - 1, prev, obstacles, dp); if prev obstacles.len() || obstacles[prev] obstacles[ui] { res res.max(1 dfs(i - 1, ui, obstacles, dp)); } dp[ui][prev] res; res } dfs(n as i32 - 1, n, obstacles, mut dp); let mut res vec![1i32; n]; for i in 1..n { res[i] 1 dp[i - 1][i]; } res } }时间与空间复杂度时间复杂度$O(n ^ 2)$状态数为 $n \times (n1)$每个状态转移为常数时间空间复杂度$O(n ^ 2)$需要存储整张记忆化表dp。注意dp表是在dfs(n - 1, n)时顺带填满的最终答案并不直接等于某个单一状态而是逐位由1 dp[i - 1][i]拼出——这对应以i结尾的最长序列 前i-1个元素中可衔接的最优前缀 1。2. 动态规划二分搜索—— 方案 I预分配数组直觉可以用二分搜索把 LIS 类问题优化到 O(n log n)。维护一个dp数组其中dp[i]表示所有长度为i 1的有效序列中最小的结尾元素值。对每个新元素用二分搜索找到它应插入的位置第一个大于它的元素位置该位置即以此元素结尾的最长有效赛道长度随后用当前值更新该位置使各长度序列尽可能可扩展。算法步骤初始化大小为n 1的dp数组全部填充一个大值如10^8表示该长度尚无序列遍历每个障碍物用二分搜索找到dp中第一个大于当前障碍物的下标index该下标即以当前位置结尾的最长有效赛道所对应的长度长度 index 1用当前障碍物值更新dp[index]把index 1写入结果数组返回结果数组。from typing import List import bisect class Solution: def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) - List[int]: res [] dp [10**8] * (len(obstacles) 1) for num in obstacles: index bisect.bisect(dp, num) # 第一个 num 的位置 res.append(index 1) dp[index] num return resimport java.util.Arrays; public class Solution { public int[] longestObstacleCourseAtEachPosition(int[] obstacles) { int n obstacles.length; int[] res new int[n]; int[] dp new int[n 1]; Arrays.fill(dp, (int) 1e8); for (int i 0; i n; i) { int index upperBound(dp, obstacles[i]); res[i] index 1; dp[index] obstacles[i]; } return res; } private int upperBound(int[] dp, int target) { int left 0, right dp.length; while (left right) { int mid left (right - left) / 2; if (dp[mid] target) { right mid; } else { left mid 1; } } return left; } }#include vector #include algorithm using namespace std; class Solution { public: vectorint longestObstacleCourseAtEachPosition(vectorint obstacles) { int n obstacles.size(); vectorint res(n); vectorint dp(n 1, 1e8); for (int i 0; i n; i) { int index upper_bound(dp.begin(), dp.end(), obstacles[i]) - dp.begin(); res[i] index 1; dp[index] obstacles[i]; } return res; } };class Solution { /** * param {number[]} obstacles * return {number[]} */ longestObstacleCourseAtEachPosition(obstacles) { let n obstacles.length; let res new Array(n).fill(0); let dp new Array(n 1).fill(1e8); const upperBound (dp, target) { let left 0, right dp.length; while (left right) { let mid Math.floor((left right) / 2); if (dp[mid] target) { right mid; } else { left mid 1; } } return left; }; for (let i 0; i n; i) { let index upperBound(dp, obstacles[i]); res[i] index 1; dp[index] obstacles[i]; } return res; } }public class Solution { public int[] LongestObstacleCourseAtEachPosition(int[] obstacles) { int n obstacles.Length; int[] res new int[n]; int[] dp new int[n 1]; Array.Fill(dp, (int)1e8); for (int i 0; i n; i) { int index UpperBound(dp, obstacles[i]); res[i] index 1; dp[index] obstacles[i]; } return res; } private int UpperBound(int[] dp, int target) { int left 0, right dp.Length; while (left right) { int mid left (right - left) / 2; if (dp[mid] target) { right mid; } else { left mid 1; } } return left; } }import sort func longestObstacleCourseAtEachPosition(obstacles []int) []int { n : len(obstacles) res : make([]int, n) dp : make([]int, n1) for i : range dp { dp[i] 1e8 } for i : 0; i n; i { index : sort.Search(len(dp), func(j int) bool { return dp[j] obstacles[i] }) res[i] index 1 dp[index] obstacles[i] } return res }class Solution { fun longestObstacleCourseAtEachPosition(obstacles: IntArray): IntArray { val n obstacles.size val res IntArray(n) val dp IntArray(n 1) { 1e8.toInt() } for (i in 0 until n) { val index upperBound(dp, obstacles[i]) res[i] index 1 dp[index] obstacles[i] } return res } private fun upperBound(dp: IntArray, target: Int): Int { var left 0 var right dp.size while (left right) { val mid left (right - left) / 2 if (dp[mid] target) { right mid } else { left mid 1 } } return left } }class Solution { func longestObstacleCourseAtEachPosition(_ obstacles: [Int]) - [Int] { let n obstacles.count var res Int var dp Int, count: n 1) for i in 0..n { let index upperBound(dp, obstacles[i]) res[i] index 1 dp[index] obstacles[i] } return res } private func upperBound(_ dp: [Int], _ target: Int) - Int { var left 0 var right dp.count while left right { let mid left (right - left) / 2 if dp[mid] target { right mid } else { left mid 1 } } return left } }impl Solution { pub fn longest_obstacle_course_at_each_position(obstacles: Veci32) - Veci32 { let n obstacles.len(); let mut res vec![0i32; n]; let mut dp vec![i32::MAX; n 1]; for i in 0..n { let index dp.partition_point(|x| x obstacles[i]); res[i] index as i32 1; dp[index] obstacles[i]; } res } }时间与空间复杂度时间复杂度$O(n \log n)$每个元素一次二分查找空间复杂度$O(n)$。仓库中的对应实现仓库 Kotlin 实现 正是本方案在 LeetCode 竞赛环境下的直接落地它用Integer.MAX_VALUE填充dp作为无穷大哨兵并通过手写的闭包binarySearch寻找第一个大于等于n的位置再 1的等价上界最终res[i] insert 1、dp[insert] n。可见方案 I 的预分配思路在实际提交中是主流选择。3. 动态规划二分搜索—— 方案 II动态增长数组直觉这是对方案 I 的空间优化版本。不再预分配n 1大小的数组而是从一个空数组出发、按需增长。当新元素能延长当前已知最长序列时直接追加否则覆盖既有位置。这样数组占用的空间只与最长子序列的长度成正比而不是与输入规模n成正比。算法步骤初始化空数组dp遍历每个障碍物用二分搜索找到dp中第一个大于当前障碍物的下标index若index恰好等于dp当前长度说明构成了新的最长序列把当前障碍物append到末尾否则用当前障碍物覆盖dp[index]把index 1写入结果数组返回结果数组。from typing import List import bisect class Solution: def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) - List[int]: res [] dp [] for num in obstacles: index bisect.bisect_right(dp, num) # 第一个 num 的位置 res.append(index 1) if index len(dp): dp.append(num) else: dp[index] num return resimport java.util.ArrayList; import java.util.List; public class Solution { public int[] longestObstacleCourseAtEachPosition(int[] obstacles) { int n obstacles.length; int[] res new int[n]; ListInteger dp new ArrayList(); for (int i 0; i n; i) { int index upperBound(dp, obstacles[i]); res[i] index 1; if (index dp.size()) { dp.add(obstacles[i]); } else { dp.set(index, obstacles[i]); } } return res; } private int upperBound(ListInteger dp, int target) { int left 0, right dp.size(); while (left right) { int mid left (right - left) / 2; if (dp.get(mid) target) { right mid; } else { left mid 1; } } return left; } }#include vector #include algorithm using namespace std; class Solution { public: vectorint longestObstacleCourseAtEachPosition(vectorint obstacles) { int n obstacles.size(); vectorint res(n); vectorint dp; for (int i 0; i n; i) { int index upper_bound(dp.begin(), dp.end(), obstacles[i]) - dp.begin(); res[i] index 1; if (index dp.size()) { dp.push_back(obstacles[i]); } else { dp[index] obstacles[i]; } } return res; } };class Solution { /** * param {number[]} obstacles * return {number[]} */ longestObstacleCourseAtEachPosition(obstacles) { let n obstacles.length; let res new Array(n).fill(0); let dp []; const upperBound (dp, target) { let left 0, right dp.length; while (left right) { let mid Math.floor((left right) / 2); if (dp[mid] target) { right mid; } else { left mid 1; } } return left; }; for (let i 0; i n; i) { let index upperBound(dp, obstacles[i]); res[i] index 1; if (index dp.length) { dp.push(obstacles[i]); } else { dp[index] obstacles[i]; } } return res; } }using System.Collections.Generic; public class Solution { public int[] LongestObstacleCourseAtEachPosition(int[] obstacles) { int n obstacles.Length; int[] res new int[n]; Listint dp new Listint(); for (int i 0; i n; i) { int index UpperBound(dp, obstacles[i]); res[i] index 1; if (index dp.Count) { dp.Add(obstacles[i]); } else { dp[index] obstacles[i]; } } return res; } private int UpperBound(Listint dp, int target) { int left 0, right dp.Count; while (left right) { int mid left (right - left) / 2; if (dp[mid] target) { right mid; } else { left mid 1; } } return left; } }import sort func longestObstacleCourseAtEachPosition(obstacles []int) []int { n : len(obstacles) res : make([]int, n) dp : []int{} for i : 0; i n; i { index : sort.Search(len(dp), func(j int) bool { return dp[j] obstacles[i] }) res[i] index 1 if index len(dp) { dp append(dp, obstacles[i]) } else { dp[index] obstacles[i] } } return res }class Solution { fun longestObstacleCourseAtEachPosition(obstacles: IntArray): IntArray { val n obstacles.size val res IntArray(n) val dp mutableListOfInt() for (i in 0 until n) { val index upperBound(dp, obstacles[i]) res[i] index 1 if (index dp.size) { dp.add(obstacles[i]) } else { dp[index] obstacles[i] } } return res } private fun upperBound(dp: ListInt, target: Int): Int { var left 0 var right dp.size while (left right) { val mid left (right - left) / 2 if (dp[mid] target) { right mid } else { left mid 1 } } return left } }class Solution { func longestObstacleCourseAtEachPosition(_ obstacles: [Int]) - [Int] { let n obstacles.count var res Int var dp [Int]() for i in 0..n { let index upperBound(dp, obstacles[i]) res[i] index 1 if index dp.count { dp.append(obstacles[i]) } else { dp[index] obstacles[i] } } return res } private func upperBound(_ dp: [Int], _ target: Int) - Int { var left 0 var right dp.count while left right { let mid left (right - left) / 2 if dp[mid] target { right mid } else { left mid 1 } } return left } }impl Solution { pub fn longest_obstacle_course_at_each_position(obstacles: Veci32) - Veci32 { let n obstacles.len(); let mut res vec![0i32; n]; let mut dp: Veci32 Vec::new(); for i in 0..n { let index dp.partition_point(|x| x obstacles[i]); res[i] index as i32 1; if index dp.len() { dp.push(obstacles[i]); } else { dp[index] obstacles[i]; } } res } }时间与空间复杂度时间复杂度$O(n \log n)$空间复杂度$O(n)$但实际占用仅与最长有效赛道长度成正比通常远小于n。仓库中的对应实现仓库 C 实现 采用的就是动态增长思路的手写版本它不预先分配n 1长度的dp而是用lisSize维护当前有效长度并做了微优化——当lis[lisSize - 1] x时直接追加此时答案就是lisSize 1否则才调用手写的upperBound找到覆盖位置。这与方案 II 的先二分、命中末尾则 append在逻辑上完全等价只是把追加分支提前短路减少了一次二分查找的开销。常见陷阱Common Pitfalls误用 Lower Bound 代替 Upper Bound本题允许子序列中出现相等元素非严格递增因此必须使用upper_bound第一个大于目标的位置而不是lower_bound第一个大于等于目标的位置。若误用 lower bound相等的元素会被当作严格递增处理导致结果错误。与标准 LIS 混淆标准最长递增子序列要求元素严格递增使用lower_bound本题要求非递减允许重复二分条件随之改变。直接把标准 LIS 算法套用到本题会漏算包含连续相等元素的有效序列。仓库 经典 LIS 题解 与 Python 实现 展示了严格的nums[i] nums[j]条件可作为对比参照差别仅在于与、upper_bound与lower_bound的一处取舍。忘记更新 DP 数组用二分找到插入位置后必须用当前元素更新dp数组。若漏掉这一步算法将无法维护每个长度对应的最优结尾值后续元素的计算结果将整体错误。返回下标而非长度二分返回的是dp数组中的下标而答案是最长有效赛道的长度。由于dp是 0 基索引下标index对应长度为index 1的序列所以每个位置的结果必须是index 1。直接返回index会造成全部答案差 1。未正确处理首元素第一个障碍物之前没有任何元素其赛道长度恒为 1。递归版本尤其要注意基准情形与结果构造如res[0] 1否则容易初始化错误或漏算。三种方案横向对比与选型建议方案核心思路时间复杂度空间复杂度适用场景1. 自顶向下 DP记忆化搜索枚举选/不选O(n²)O(n²)理解状态转移、小规模输入、教学演示2. 二分 DP预分配dp[i]记录长度i1的最小结尾值O(n log n)O(n)竞赛与工程中的主流解法见 Kotlin 实现3. 二分 DP动态增长空数组按需追加/覆盖O(n log n)O(n)实际为最长序列长度空间敏感场景、极致简洁实现见 C 实现在实际编码中方案二、方案三均只需一次遍历加一次二分代码量小、边界简单是面试与竞赛的首选方案一则更适合作为理解状态与转移的教学入口。无论选择哪种方案都要牢牢抓住两个核心点非严格递增允许相等决定必须使用 upper bound答案返回的是长度而非下标。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考