Python程式：查詢最長子列表，其中最小值和最大值之間的差小於k

假設我們有一個名為nums的數字列表和另一個值k，我們需要找到最長子列表的長度，其中最大元素和最小元素之間的絕對差≤k。

因此，如果輸入類似於nums = [2, 4, 6, 10] k = 4，則輸出將為3，因為我們可以選擇[2, 4, 6]，這裡絕對差為4。

為了解決這個問題，我們將遵循以下步驟：

  • 建立兩個雙端佇列maxd，mind
  • i := 0，res := 1
  • 對於每個索引j和值a在A中，執行以下操作：
    • 當maxd不為空且a > maxd的最後一個元素時，執行以下操作：
      • 從maxd刪除最後一個元素
    • 當mind不為空且a < mind的最後一個元素時，執行以下操作：
      • 從mind刪除最後一個元素
    • 將a插入到maxd的末尾
    • 將a插入到mind的末尾
    • 當maxd[0] - mind[0] > limit時，執行以下操作：
      • 如果maxd[0]與A[i]相同，則
        • 從maxd的左側刪除專案
      • 如果mind[0]與A[i]相同，則
        • 從mind的左側刪除專案
      • i := i + 1
    • res := res和(j - i + 1)中的最大值
  • 返回res

讓我們看看下面的實現以更好地理解：

示例

 即時演示

from collections import deque, defaultdict
class Solution:
   def solve(self, A, limit):
      maxd = deque()
      mind = deque()
      i = 0
      res = 1
      for j, a in enumerate(A):
         while maxd and a > maxd[-1]:
            maxd.pop()
         while mind and a < mind[-1]:
            mind.pop()
         maxd.append(a)
         mind.append(a)
         while maxd[0] - mind[0] > limit:
            if maxd[0] == A[i]:
               maxd.popleft()
            if mind[0] == A[i]:
               mind.popleft()
            i += 1
            res = max(res, j - i + 1)
      return res
ob = Solution()
nums = [2, 4, 6, 10]
k = 4
print(ob.solve(nums, k))

輸入

[2, 4, 6, 10], 4

輸出

3

更新於: 2020年11月19日

199 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告