[閒聊] leetcode 大師請進已回收

看板Marginalman作者 (動物園 公告)時間1年前 (2024/05/06 21:12), 編輯推噓6(6推 0噓 5→)
留言11則, 6人參與, 1年前最新討論串1/8 (看更多)
幫我解題 我有一組不重複的正整數一維陣列 每次行動可以將某個數字插入另一個數字的後面 行動以一個長度為二的陣列[a, b]表示 a 插入 b 後面 如果元素要放到開頭就以插入 0 表示 求最小行動數的二維陣列 ex: 題目: [1, 3, 7, 9, 5, 2] 答: [[2, 1], [5, 3]] 題目: [9, 7, 5, 3, 1] 答: [[1, 0], [3, 1], [5, 3], [7, 5]] 或是 [[7, 0], [5, 0], [3, 0], [1, 0]] 題目的陣列長度是三位數 元素都是正整數(其實沒差，不過限定正整數比較好設定排頭) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.227.135 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715001130.A.848.html
→
05/06 21:21, 1年前 , 1F
看起來是monotonic stack
05/06 21:21, 1F
推
05/06 21:22, 1年前 , 2F
monotonic stack+1
05/06 21:22, 2F
推
05/06 21:23, 1年前 , 3F
同上
05/06 21:23, 3F
推
05/06 21:26, 1年前 , 4F
nlogn 感覺可以欸 每進一個數字 往回找到位子插入 可
05/06 21:26, 4F
→
05/06 21:26, 1年前 , 5F
以用二分搜找位子
05/06 21:26, 5F
→
05/06 21:27, 1年前 , 6F
n感覺好像不行了 因為要知道插進去哪裡
05/06 21:27, 6F
推
05/06 21:33, 1年前 , 7F
直接用upper_bound()或lower_bound() 對不起
05/06 21:33, 7F
推
05/06 21:34, 1年前 , 8F
我粗看是想到n**2
05/06 21:34, 8F
→
05/06 21:35, 1年前 , 9F
我找一下monotonic stack 沒聽過這玩意兒
05/06 21:35, 9F
推
05/06 21:44, 1年前 , 10F
三位數可以直接counting sort了
05/06 21:44, 10F
→
05/06 22:44, 1年前 , 11F
元素大小未知，數量是三位數
05/06 22:44, 11F
‣ 更多 ZooseWu 的文章
文章代碼(AID): #1cEDSgX8 (Marginalman)
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 8 篇)：
排序： 最新先 | 最舊先 | 留言數
在新視窗開啟完整討論串 (共8篇)
‣ 更多 ZooseWu 的文章
文章代碼(AID): #1cEDSgX8 (Marginalman)