夏•◡•センパイ
@davidegg
分享
Wed, Aug 16, 2023 1:45 PM
1
ͨ•ͦ◡ͩ•ͥng日記 042

239. Sliding Window Maximum
夏•◡•センパイ
@davidegg
Wed, Aug 16, 2023 1:45 PM
因為吃藥會有點想睡 所以下班之後直接躺了一下
結果做了奇怪的夢= =
夏•◡•センパイ
@davidegg
Wed, Aug 16, 2023 1:48 PM
Wed, Aug 16, 2023 1:48 PM
夢裡我在排船?桃?場物販
因為買滿10萬會送一次桃桃手渡
所以我就邊排邊用動態規劃算要怎樣買到十萬最划算
(？？？？)
然後算了半個多小時之後已經決定好要買什麼了
卻發現物販隊列根本沒在動
往前看，發現一直有鳳梨在最前列插隊
我就叫住路過的staff問他說為什麼那些人可以插隊
staff：我們這裡是double ended queue喔
夏•◡•センパイ
@davidegg
Wed, Aug 16, 2023 1:49 PM
然後我就醒了= =
夏•◡•センパイ
@davidegg
Wed, Aug 16, 2023 1:49 PM
說好的手渡呢
幹你deque
夏•◡•センパイ
@davidegg
Wed, Aug 16, 2023 1:50 PM
Sliding Window Maximum - LeetCode
夏•◡•センパイ
@davidegg
Wed, Aug 16, 2023 1:51 PM
看解答才知道queue還能這樣用... 好酷

https://images.plurk.com/4OjNgVg6JUh9xhbEpeB3UX.png
夏•◡•センパイ
@davidegg
Wed, Aug 16, 2023 1:53 PM
感覺hard解不出來的時候
都已經不是程式知識的問題
是數學問題吧QQ

像這題的關鍵是

一個window內某個元素
如果數值比同窗戶後面的某元素小
就不可能成為局部最大值

不看提示就想到的人也太鬼了吧
漲芙
@Dephillia
Wed, Aug 16, 2023 1:55 PM
刷題有夠像在練奧林匹亞的手感
無冬夜😈Act-4🥹
@tw0517tw
Wed, Aug 16, 2023 1:57 PM
鳳梨XDDDD
夏•◡•センパイ
@davidegg
Wed, Aug 16, 2023 1:58 PM
漲芙 : 數奧還是資奧 我都沒玩過
夏•◡•センパイ
@davidegg
Wed, Aug 16, 2023 1:58 PM
無冬夜😈Act-4🥹 : 我現在有點想不起來夢裡的我是人還是鳳梨...
漲芙
@Dephillia
Wed, Aug 16, 2023 1:58 PM
Wed, Aug 16, 2023 1:59 PM
資奧就這種題目再難一點（
然後可能可以組合成一個大題目
夏•◡•センパイ
@davidegg
Wed, Aug 16, 2023 1:59 PM
慘 我的數學比高中生還爛
夏•◡•センパイ
@davidegg
Wed, Aug 16, 2023 2:03 PM
想說打鐵趁熱(?)就跑去再刷了一題標註Monotonic Deque的題目

862. Shortest Subarray with Sum at Least K
Shortest Subarray with Sum at Least K - LeetCode

前一題是遍歷出移動區間的局部最大值
這題是找總和至少為給定值的最小區間
貓熊◢
@wayne0515
Wed, Aug 16, 2023 2:04 PM
看到hard我就直接看解說了 一定是我沒學過的演算法或資料結構
夏•◡•センパイ
@davidegg
Wed, Aug 16, 2023 2:05 PM
看起來有點像 但這題又更像hard一點
資料要先處理成到目前為止的總和
然後區間頭尾的總和相減就是區間內的總和
...誰想的到= =
夏•◡•センパイ
@davidegg
Wed, Aug 16, 2023 2:07 PM
貓熊◢ : 草
queue我是知道
不過我只有用它做過BFS

以前一直沒想過雙端駐列能幹嘛
想說不就排隊 一進一出剛剛好

結果向這兩題就需要把排尾的人趕走
就變成需要double ended queue...
載入新的回覆