Pythonで最も競争力の高い部分列を見つけるプログラム

問題の概要

配列 nums と整数 k が与えられたとき、nums からサイズ k の「最も競争力のある」部分列を求めます。ここで、ある部分列 s1 が同じサイズの別の部分列 s2 より競争力が高いとは、s1 と s2 が初めて異なる位置において、s1 の数値が s2 の対応する数値よりも小さいことを意味します。

例えば、入力が nums = [4,6,3,7]、k = 2 の場合、出力は [3,7] となります。サイズ 2 のすべての部分列 {[4,6], [4,3], [4,7], [6,3], [6,7], [3,7]} の中で、[3,7] が最も競争力の高い部分列だからです。

解法アプローチ：スタックを使った貪欲法

この問題は、スタックを利用した貪欲法（グリーディ法）で効率的に解くことができます。基本的な考え方は、「後から来るより小さい数と入れ替えられる限り、大きい数を削除していく」というものです。具体的な手順は以下の通りです。

• attempts（削除できる残り回数）:= nums のサイズ − k
• stack := 空のリストを作成する
• nums の各要素 num に対して以下を繰り返す：
  • stack が空でなく、num がスタックの先頭要素より小さく、attempts > 0 である間、スタックから要素を pop し、attempts を 1 減らす
  • num をスタックに push する
• 最後に、スタックの先頭から k 個の要素を返す

このアルゴリズムの時間計算量は O(n) です。各要素は最大でも一度 push され、一度しか pop されないため、大きな入力サイズに対しても非常に高速に動作します。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

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]

このように、スタックを活用することで、全ての部分列を列挙せずとも線形時間で最も競争力の高い部分列を効率よく求めることができます。