給定整數陣列
obstacles，對每個位置i，找出以obstacles[i]結尾的最長非遞減子序列長度（元素必須從索引 0 到 i 中選取且保持原順序）。
Example:
Input: obstacles = [1,2,3,2] Output: [1,2,3,3]
Intuition
TIP
LIS 的非遞減版本 — 用 patience sorting + 二分搜尋，對每個位置算出以它結尾的最長非遞減子序列。
- 和 LIS 類似，但條件是「非遞減」（允許相等）
- 維護
tails陣列，用 upper bound 而非 lower bound（因為允許相等） - 每個元素插入位置就是以它結尾的最長非遞減子序列長度
Approaches
1. Memoization (Top-Down LIS) — O(n^2) / O(n)
- Idea: 定義
f(i)= 以obstacles[i]結尾的最長非遞減子序列長度，遞迴尋找前面所有j滿足obstacles[j] <= obstacles[i]的最大f(j)，加 memo - Time:
O(n^2)- 每個狀態 O(n) 轉移，共 n 個狀態 - Space:
O(n)- memo + 遞迴堆疊
class Solution {
fun longestObstacleCourseAtEachPosition(obstacles: IntArray): IntArray {
val n = obstacles.size
val memo = IntArray(n) { -1 }
fun dp(i: Int): Int {
if (memo[i] != -1) return memo[i]
var best = 1
for (j in 0 until i) {
if (obstacles[j] <= obstacles[i]) {
best = maxOf(best, dp(j) + 1)
}
}
memo[i] = best
return best
}
return IntArray(n) { dp(it) }
}
}2. Bottom-Up DP O(n^2) (TLE) — O(n^2) / O(n)
- Idea: 對每個位置掃描前面所有 <= 它的元素，取最長 + 1
- Time:
O(n^2) - Space:
O(n)
class Solution {
fun longestObstacleCourseAtEachPosition(obstacles: IntArray): IntArray {
val n = obstacles.size
val dp = IntArray(n) { 1 }
for (i in 1 until n) {
for (j in 0 until i) {
if (obstacles[j] <= obstacles[i]) {
dp[i] = maxOf(dp[i], dp[j] + 1)
}
}
}
return dp
}
}⭐ 3. Patience Sorting + Binary Search (Upper Bound) — O(n log n) / O(n)
- Idea: 維護非遞減的
tails陣列，用 upper bound 二分搜尋確定插入位置 - Time:
O(n log n) - Space:
O(n)
class Solution {
fun longestObstacleCourseAtEachPosition(obstacles: IntArray): IntArray {
val n = obstacles.size
val ans = IntArray(n)
val tails = mutableListOf<Int>()
for (i in 0 until n) {
val num = obstacles[i]
// upper bound：找第一個 > num 的位置
var lo = 0; var hi = tails.size
while (lo < hi) {
val mid = (lo + hi) / 2
if (tails[mid] <= num) lo = mid + 1 else hi = mid
}
ans[i] = lo + 1
if (lo == tails.size) tails.add(num) else tails[lo] = num
}
return ans
}
}🔑 Takeaways
- Pattern: LIS 變體（非遞減）— 二分搜尋用 upper bound 而非 lower bound
- Key trick: 嚴格遞增用 lower bound（第一個 >=），非遞減用 upper bound（第一個 >）；每個元素的插入位置直接就是答案