Re: [閒聊] leetcode 大師請進已回收
※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言：
: 1.先把陣列分成兩堆，遞增的記住他們的索引變一個單調堆疊，非遞增的記住他們的值。
: 2.把非遞增的值排序。
: 3.從最大數字x開始處理非遞增的值，如果stack頂端大於x就把頂端元素pop，如果比較小
: 就表示要插到頂端的右邊，如果單調堆疊已經空就插到0，因為是從大的元素開始插入
: 所以右邊的索引變怎樣就不用管了。
: py code
: -------------------------------------------
: def min_actions(arr):
: res = []
: s = []
: ls = []
: for i in range(len(arr)):
: if not s or arr[s[-1]] < arr[i]:
: s.append(i)
: else:
: ls.append(arr[i])
這裡一般要維護 monotonic stack 的話應該是要在嘗試 s.append(i) 的時候 pop
while s and arr[s[-1]] < arr[i]:
del s[-1]
s.append(i)
你這樣的寫法就只有找到第一個遞增 subsequence 而已
不一定會是最長的 像是 [1,7,9,2,3,4] 的話
會找到 s = [1,7,9], ls = [2,3,4]
: ls.sort()
: while ls:
: while s and arr[s[-1]] > ls[-1]:
: s.pop()
: x = ls.pop()
: if not s:
: res.append((0, x))
: else:
: res.append((s[-1] + 1, x))
: return res
: -------------------------------------------
: 我亂寫的 那兩個測資有過 複雜度是O(nlogn) 可能有bug 對不起
所以這題應該是要先找 longest increasing subsequence (LIS)
確保更改順序的元素量最小
然後找 LIS 和 monotonic stack 應該也沒有關係
monotonic stack 通常是拿來找每個元素往前第一個比自己大/小的元素在哪
LIS 在這 https://leetcode.com/problems/longest-increasing-subsequence/
不過只有找長度 討論區有記 path 找到實際 LIS 的版本 也是 O(nlog(n))
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.164.140.99 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715007154.A.FDD.html
→
05/06 22:53,
1年前
, 1F
05/06 22:53, 1F
→
05/06 22:54,
1年前
, 2F
05/06 22:54, 2F
→
05/06 22:58,
1年前
, 3F
05/06 22:58, 3F
※ 編輯: pandix (1.164.140.99 臺灣), 05/06/2024 23:03:49
→
05/06 23:03,
1年前
, 4F
05/06 23:03, 4F
→
05/06 23:04,
1年前
, 5F
05/06 23:04, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 8 篇)：