1. 題目鏈接

1964. 找出到每個位置為止最長的有效障礙賽跑路線 - 力扣（LeetCode）

2. 題目描述

你打算構建一些障礙賽跑路線。給你一個 下標從 0 開始 的整數數組 obstacles ，數組長度為 n ，其中 obstacles[i] 表示第 i 個障礙的高度。

對于每個介于 0 和 n - 1 之間（包含 0 和 n - 1）的下標 i ，在滿足下述條件的前提下，請你找出 obstacles 能構成的最長障礙路線的長度：

• 你可以選擇下標介于 0 到 i 之間（包含 0 和 i）的任意個障礙。
• 在這條路線中，必須包含第 i 個障礙。
• 你必須按障礙在 obstacles 中的 出現順序 布置這些障礙。
• 除第一個障礙外，路線中每個障礙的高度都必須和前一個障礙 相同 或者 更高 。

返回長度為 n 的答案數組 ans , ans[i] 是上面所述的下標 i 對應的最長障礙賽跑路線的長度

3. 題目示例

示例 1 :

輸入：obstacles = [1,2,3,2]
輸出：[1,2,3,3]
解釋：每個位置的最長有效障礙路線是：
- i = 0: [1], [1] 長度為 1
- i = 1: [1,2], [1,2] 長度為 2
- i = 2: [1,2,3], [1,2,3] 長度為 3
- i = 3: [1,2,3,2], [1,2,2] 長度為 3

示例 2 :

輸入：obstacles = [2,2,1]
輸出：[1,2,1]
解釋：每個位置的最長有效障礙路線是：
- i = 0: [2], [2] 長度為 1
- i = 1: [2,2], [2,2] 長度為 2
- i = 2: [2,2,1], [1] 長度為 1

示例 3 :

輸入：obstacles = [3,1,5,6,4,2]
輸出：[1,1,2,3,2,2]
解釋：每個位置的最長有效障礙路線是：
- i = 0: [3], [3] 長度為 1
- i = 1: [3,1], [1] 長度為 1
- i = 2: [3,1,5], [3,5] 長度為 2, [1,5] 也是有效的障礙賽跑路線
- i = 3: [3,1,5,6], [3,5,6] 長度為 3, [1,5,6] 也是有效的障礙賽跑路線
- i = 4: [3,1,5,6,4], [3,4] 長度為 2, [1,4] 也是有效的障礙賽跑路線
- i = 5: [3,1,5,6,4,2], [1,2] 長度為 2

4. 解題思路

1. 問題描述：給定一個整數數組obstacles，要求對于每個位置i，計算以obstacles[i]結尾的最長非遞減子序列的長度。
2. 方法選擇：本題可以使用動態規劃和二分查找的結合方法。動態規劃用于記錄當前的最長非遞減子序列，二分查找用于高效更新和維護這個序列。
3. 關鍵步驟：
   • 維護**dp**列表：dp列表用于存儲當前的最長非遞減子序列。對于每個元素v = obstacles[i]，在dp中找到第一個大于等于v + 1的位置p：
     • 如果p < dp.size()，說明可以替換dp[p]為v，以保持dp的非遞減性。
     • 否則，將v添加到dp末尾，擴展最長非遞減子序列。
   • 結果計算：以obstacles[i]結尾的最長非遞減子序列的長度為p + 1，直接存入結果數組ans。
4. 二分查找優化：binarySearch函數使用二分查找在dp中找到第一個大于等于target的位置，時間復雜度為O(log k)（k為當前dp的長度）。
   
   

5. 題解代碼

public class Solution {public int[] longestObstacleCourseAtEachPosition(int[] obstacles) {// 初始化結果數組，ans[i]表示以obstacles[i]結尾的最長障礙子序列的長度int[] ans = new int[obstacles.length];// dp列表用于維護當前的最長遞增子序列List<Integer> dp = new ArrayList<>();for (int i = 0; i < obstacles.length; i++) {int v = obstacles[i];// 在dp中找到第一個大于等于v+1的位置int p = binarySearch(dp, v + 1);if (p < dp.size()) {// 如果找到，用v替換該位置的元素dp.set(p, v);} else {// 否則將v添加到dp末尾dp.add(v);}// 當前最長障礙子序列的長度為p+1ans[i] = p + 1;}return ans;}// 二分查找：在list中找到第一個大于等于target的位置private int binarySearch(List<Integer> list, int target) {int left = 0;int right = list.size();while (left < right) {int mid = left + (right - left) / 2;if (list.get(mid) < target) {left = mid + 1;} else {right = mid;}}return left;}
}

6. 復雜度分析

1. 時間復雜度：
   • 遍歷數組obstacles需要O(n)時間。
   • 對于每個元素，二分查找binarySearch需要O(log k)時間（k為當前dp的長度）。
   • 最壞情況下，dp的長度可能達到n，因此總時間復雜度為O(n log n)。
2. 空間復雜度：
   • dp列表最多存儲n個元素，因此空間復雜度為O(n)。
   • 結果數組ans也需要O(n)空間。
   • 因此，總空間復雜度為O(n)。