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

2022.02.12
LeetCode

https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

Solution

我們使用 min_dq, max_dq 兩個 queue
依照下列步驟去維護min_dq, max_dq：

把 min_dq, max_dq 前方與當前數字 nums[i] 差距超過 limit 的元素 pop 掉
把 min_dq, max_dq 後方大於/小於當前數字 nums[i] 的元素 pop 掉
將 nums[i] push 進 min_dq, max_dq

如此，在 index i 時的 min_dq, max_dq 將會符合下列條件：

最後一個元素一定是 nums[i]
min_dq, max_dq 中的 values 將會是不降序/不升序排列（單調遞增/遞減排列）
而 indices 將會是嚴格升序/降序排列（嚴格遞增/遞減排列）
且 min_dq, max_dq 最前和最後的元素差距一定 <= limit

若在前方被 pop 掉的最後一個元素素的 index 名為 j （取 line 9, 10 和 12, 13 較大的一方）
則 nums[j + 1:i + 1]就會是中止於 i 的符合本題條件的最長子序列

class Solution:
  def longestSubarray(self, nums: List[int], limit: int) -> int:
    min_dq = collections.deque()
    max_dq = collections.deque()

    start = max_len = 0

    for i in range(len(nums)):
      while min_dq and abs(nums[i] - min_dq[0][0]) > limit:
        start = min_dq.popleft()[1] + 1

      while max_dq and abs(nums[i] - max_dq[0][0]) > limit:
        start = max(start, max_dq.popleft()[1] + 1)

      while min_dq and min_dq[-1][0] >= nums[i]:
        min_dq.pop()
      min_dq.append([nums[i], i])

      while max_dq and max_dq[-1][0] <= nums[i]:
        max_dq.pop()
      max_dq.append([nums[i], i])

      max_len = max(max_len, i - start + 1)

    return max_len

Last Updated on 2023/08/16 by A1go