1964. Find the Longest Valid Obstacle Course at Each Position

Hard
Description

給定整數陣列 obstacles，對每個位置 i，找出以 obstacles[i] 結尾的最長非遞減子序列長度（元素必須從索引 0 到 i 中選取且保持原順序）。

Example:

Input: obstacles = [1,2,3,2] Output: [1,2,3,3]

Intuition#

LIS 的非遞減版本 — 用 patience sorting + 二分搜尋，對每個位置算出以它結尾的最長非遞減子序列。

  • 和 LIS 類似，但條件是「非遞減」（允許相等）
  • 維護 tails 陣列，用 upper bound 而非 lower bound（因為允許相等）
  • 每個元素插入位置就是以它結尾的最長非遞減子序列長度

Approaches#

1: DP O(n^2) (TLE)#

  • 概念: 對每個位置掃描前面所有 <= 它的元素，取最長 + 1
  • 時間複雜度: O(n^2)
  • 空間複雜度: 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
    }
}

⭐2: Patience Sorting + Binary Search (Upper Bound)#

  • 概念: 維護非遞減的 tails 陣列，用 upper bound 二分搜尋確定插入位置
  • 時間複雜度: O(n log n)
  • 空間複雜度: 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
  • 關鍵技巧: 嚴格遞增用 lower bound（第一個 >=），非遞減用 upper bound（第一個 >）；每個元素的插入位置直接就是答案