Pythonで最も競争力のあるサブシーケンスを見つけるためのプログラム

配列numsと別の値kがあるとすると、サイズkのnumsの最も競合するサブシーケンスを見つける必要があります。ここで、サブシーケンスs1は、サブシーケンスs2（同じサイズ）よりも競争力があります。これは、s1とs2が異なる最初の位置で、サブシーケンスs1の数がs2の対応する数よりも少ない場合です。

したがって、入力がnums =[4,6,3,7] k =2のような場合、サイズ2のすべてのサブシーケンスの中で{[4,6]、[4、 3]、[4,7]、[6,3]、[6,7]、[3,7]}、[3,7]が最も競争力があります。

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

• 試行：=numsのサイズ-k
• スタック：=新しいリスト
• numsの各numについて、実行します
  • スタックが空ではなく、num <スタックの最上位で、> 0を試行している間、実行
    • スタックから要素をポップ
    • 試行：=試行-1
  • numをスタックにプッシュします
• スタックの上位k個の要素を返す

例

理解を深めるために、次の実装を見てみましょう-

def solve(nums, k):
   attempts = len(nums) - k
   stack = []
   for num in nums:
      while stack and num < stack[-1] and attempts > 0:
         stack.pop()
         attempts -= 1
      stack.append(num)

   return stack[:k]

nums = [4,6,3,7]
k = 2
print(solve(nums, k))

入力

[4,6,3,7], 2

出力

[3,7]