Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to
Limit

給一個array nums

請回傳最長的subarray的長度

該subarray裡的任兩個元素差值不能超過limit

思路:

sliding window，用兩個index:l、r代表現在window的左右邊界

建立兩個monotonic stack去記錄最大和最小值

當最大跟最小值超過limit時，l就往右移

記得要去維護monotonic stack裡的元素，保持這些元素都在window裡

這樣就可以得到答案了

golang code :

func longestSubarray(nums []int, limit int) int {
        maxstack, minstack := []int{}, []int{}
        n,  l := len(nums), 0
        for i := 0; i < n; i++ {
                for len(maxstack) > 0 && nums[i] > nums[maxstack[len(maxstack)-1]] {
                        maxstack = maxstack[:len(maxstack)-1]
                }
                maxstack = append(maxstack, i)
                for len(minstack) > 0 && nums[i] < nums[minstack[len(minstack)-1]] {
                        minstack = minstack[:len(minstack)-1]
                }
                minstack = append(minstack, i)
                if nums[maxstack[0]]-nums[minstack[0]] > limit {
                        for l >= maxstack[0] {
                                maxstack = maxstack[1:]
                        }
                        for l >= minstack[0] {
                                minstack = minstack[1:]
                        }
                        l++
                }
        }
        return n - l
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.75.61.206 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1719224486.A.BC1.html
→ Furina: 大師
推 oin1104: 送我模型
→ SecondRun: 是要刷幾題
→ JIWP: 這是昨天的
推 DJYOMIYAHINA: 你怎麼這麼猛
→ JIWP: 我都偷看答案