Re: [閒聊] 每日leetcode

[DJYOMIYAHINA (通通打死)]

今天的好難喔
看安殺才知道 multiset跟monotonic deque這兩個東西==
聽都沒聽過

直接照抄答案

用兩個monotonic deque來維護最大值和最小值。
increaseDeque[0] = 最小值
decreaseDeque[0] = 最大值

新元素加入時，對於最大值deque，不用保留比新元素num[j]小的值，因為這些值在j之前
，當子陣列跨過j時，這些值不會影響後面的答案，因此全部pop出去再append新元素。

相反地，對於最小值deque，不用保留比新元素大的值，先把比新元素大的值全部pop出去
再append，這樣才能維持這兩個deque的單調遞增/遞減。

當最大值-最小值不符合條件時，需要移動left pointer。移動過程中，如果遇到當前的
最大值或最小值，則要將其從左側移出。


def longestSubarray(self, nums: List[int], limit: int) -> int:
    ans, l = 0, 0
    dec = collections.deque() # for maximum
    inc = collections.deque() # for minimum


    for r, num in enumerate(nums):
        while dec and dec[-1] < num:
            dec.pop()
        dec.append(num)

        while inc and inc[-1] > num:
            inc.pop()
        inc.append(num)

        # dec[0] == maximum in subarray
        # inc[0] == minimum in subarray
        while dec[0]-inc[0] > limit:
            if dec[0] == nums[l]:
                dec.popleft()
            if inc[0] == nums[l]:
                inc.popleft()
            l += 1

        ans = max(ans, r-l+1)

    return ans

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.146.144 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1719115649.A.926.html
推 TokiwaKurumi: 肥肥不會寫程式
※ 編輯: DJYOMIYAHINA (125.228.146.144 臺灣), 06/23/2024 12:08:53
→ DJYOMIYAHINA: 肥肥我也不會:(
推 Hinapig0519: 肥肥只會hello world
→ NCKUEECS: 別捲了
→ smart0eddie: 大師
→ sixB: 好 來寫每日ㄌ
推 oin1104: 這做法好屌 我哭了
→ deatheo: queue這個datastruct有教