Python程式：查詢滿足給定條件的最長子列表長度

假設我們有一個名為nums的數字列表，我們需要找到其中最長的子列表的長度，該子列表滿足以下條件：子列表的最小值的2倍大於子列表的最大值。

例如，如果輸入是nums = [10, 2, 6, 6, 4, 4]，則輸出為4，因為子列表[6, 6, 4, 4]是最長的滿足條件的子列表，因為2 * 4 > 6。

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

• ret := 0

• 定義兩個雙端佇列minq和maxq

• l := 0, r := 0

• 當r < nums的大小，執行以下操作：

  • n := nums[r]

  • 當minq不為空且n < nums[minq的最後一個元素]，執行以下操作：

    • 刪除minq的最後一個元素

  • 在minq的末尾插入r

  • 當maxq不為空且n > nums[maxq的最後一個元素]，執行以下操作：

    • 刪除maxq的最後一個元素

  • 在maxq的末尾插入r

  • r := r + 1

  • 當l < r且nums[minq[0]] * 2 <= nums[maxq[0]]，執行以下操作：

    • 如果minq[0]與l相同，則

      • 刪除minq的第一個元素

    • 如果maxq[0]與l相同，則

      • 刪除maxq的第一個元素

    • l := l + 1

  • ret := ret和(r - l)中的最大值

• 返回ret

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

示例

 線上演示

class Solution:
   def solve(self, nums):
      from collections import deque
      ret = 0
      minq, maxq = deque(), deque()
      l, r = 0, 0
      while r < len(nums):
         n = nums[r]
         while minq and n < nums[minq[-1]]:
            minq.pop()
      minq.append(r)
      while maxq and n > nums[maxq[-1]]:
         maxq.pop()
      maxq.append(r)
      r += 1
      while l < r and nums[minq[0]] * 2 <= nums[maxq[0]]:
         if minq[0] == l:
            minq.popleft()
         if maxq[0] == l:
            maxq.popleft()
         l += 1
      ret = max(ret, r - l)
   return ret
ob = Solution()
nums = [10, 2, 6, 6, 4, 4]
print(ob.solve(nums))

輸入

[10, 2, 6, 6, 4, 4]

輸出

4

Arnab Chakraborty

更新於： 2020年10月10日

254 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習