Re: [閒聊] 每日LeetCode
1964. Find the Longest Valid Obstacle Course at Each Position
要你對 interger array 中的每個元素
找出以他為結尾的非嚴格遞增 subsequence 最長長度是多少
Example 1:
Input: obstacles = [1,2,3,2]
Output: [1,2,3,3]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [1], [1] has length 1.
- i = 1: [1,2], [1,2] has length 2.
- i = 2: [1,2,3], [1,2,3] has length 3.
- i = 3: [1,2,3,2], [1,2,2] has length 3.
Example 2:
Input: obstacles = [2,2,1]
Output: [1,2,1]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [2], [2] has length 1.
- i = 1: [2,2], [2,2] has length 2.
- i = 2: [2,2,1], [1] has length 1.
Example 3:
Input: obstacles = [3,1,5,6,4,2]
Output: [1,1,2,3,2,2]
Explanation: The longest valid obstacle course at each position is:
- i = 0: [3], [3] has length 1.
- i = 1: [3,1], [1] has length 1.
- i = 2: [3,1,5], [3,5] has length 2. [1,5] is also valid.
- i = 3: [3,1,5,6], [3,5,6] has length 3. [1,5,6] is also valid.
- i = 4: [3,1,5,6,4], [3,4] has length 2. [1,4] is also valid.
- i = 5: [3,1,5,6,4,2], [1,2] has length 2.
思路:
1.可以想像一個畫面是檢查 obstacles[i] 時
前面已經有個 obstacles[0:i] 能組成的最長非嚴格遞增 subsequence 叫他 arr 好了
然後就直接對 arr 二分搜就好 感覺就會直接是答案了
實作的方法就是維護這個 arr
obstacles[i] 有沒有大於等於他最後一項 有的話就直接加在後面 沒有就跳過
2.這方法假如遇到 [1,3,4,2,2,2] 就算不出正解了
因為檢查到後面的 2 時 arr 會是 [1,3,4]
搜出來的 index 會一直都是 1 但其實後面的 2 有辦法找到更長的 也就是 [1,2,2,2]
所以這裡要嘗試修改能把後面的 2 考慮進去
方法也很簡單 就是 update arr[index] 成現在的數字
所以 [1,3,4,2]: arr = [1,3,4] -> [1,2,4]
[1,3,4,2,2]: arr = [1,2,4] -> [1,2,2]
[1,3,4,2,2,2]: arr = [1,2,2] -> [1,2,2,2]
也就是說 arr 的定義改變了 不是代表某個特定的 subsequence
變成 arr[i] 代表長度是 i 的 subsequence 中最後一項最小值可能是多少
因為 arr 還是維持非嚴格遞增 所以檢查 obstacles[i] 時二分搜搜到的結果
就是 arr 中小於等於 obstacles[i] 最靠右的那個 也就是長度最大的
Python code:
class Solution:
def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) ->
List[int]:
arr = []
res = []
for num in obstacles:
if not arr or arr[-1] <= num:
arr.append(num)
res.append(len(arr))
else:
idx = bisect_right(arr, num)
arr[idx] = num
res.append(idx+1)
return res
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.252.3.181 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1683497972.A.F0F.html
推
05/08 06:24,
2年前
, 1F
05/08 06:24, 1F
推
05/08 06:29,
2年前
, 2F
05/08 06:29, 2F
推
05/08 08:45,
2年前
, 3F
05/08 08:45, 3F
討論串 (同標題文章)
完整討論串 (本文為第 315 之 719 篇)：