Pythonで最小値と最大値の差がkよりも小さい最長のサブリストの長さを見つけるプログラム

numsと呼ばれる数値のリストと別の値kがあるとすると、最大要素と最小要素の絶対差が≤kである最長のサブリストの長さを見つける必要があります。

したがって、入力がnums =[2、4、6、10] k =4の場合、出力は3になります。ここで、pick [2、4、6]を選択できるため、絶対差は4です。

これを解決するには、次の手順に従います-

• 2つの両端キューmaxdを作成します。
• i：=0、res：=1
• Aの各インデックスjと値aについて、実行します
  • maxdが0ではなく、> maxdの最後の要素である場合、
    • maxdから最後の要素を削除する
  • 心は0ではなく、<心の最後の要素ですが、
    • 心から最後の要素を削除する
  • maxdの最後にaを挿入
  • 心の終わりにaを挿入
  • maxd [0] --mind [0]>制限している間、実行
    • maxd[0]がA[i]と同じ場合、
      • maxdの左側からアイテムを削除
    • mind[0]がA[i]と同じ場合、
      • 心の左からアイテムを削除する
    • i：=i + 1
  • res：=resの最大値と（j --i + 1）
• return 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