Pythonで最大値が2番目に大きい値の2倍を超えるか判定する方法

数値のリストが与えられたとき、そのリスト内の最大値が2番目に大きい値の2倍よりも大きいかどうかを判定する問題を考えてみましょう。

例を挙げると、リストが [3, 9, 6] の場合、最大値は9ですが、2番目に大きい値6の2倍である12より小さいため、結果は False になります。一方、リストが [6, 3, 15] の場合、最大値15は12（6の2倍）より大きいため、結果は True になります。

解法のアプローチ

この問題は、リストを一度だけ走査しながら「最大値」と「2番目に大きい値」を追跡することで、効率的に解くことができます。具体的な手順は以下の通りです。

• リストの要素数が2未満の場合は False を返す
• p_max（2番目に大きい値）を nums[0] と nums[1] の小さい方に設定する
• c_max（最大値）を nums[0] と nums[1] の大きい方に設定する
• i を 2 からリストの末尾まで繰り返す
  • nums[i] が p_max より大きい場合
    • nums[i] が c_max よりも大きければ、p_max を c_max に更新し、c_max を nums[i] に更新する
    • そうでなければ、p_max を nums[i] に更新する
• 最後に c_max > p_max * 2 の判定結果を返す

それでは、実際の実装を見てみましょう。

実装例

class Solution:
    def solve(self, nums):
        if len(nums) < 2:
            return False
        p_max = min(nums[0], nums[1])
        c_max = max(nums[0], nums[1])
        for i in range(2, len(nums)):
            if nums[i] > p_max:
                if nums[i] > c_max:
                    p_max = c_max
                    c_max = nums[i]
                else:
                    p_max = nums[i]
        return c_max > p_max * 2

ob = Solution()
nums = [3, 6, 15]
print(ob.solve(nums))

入力

[3, 6, 15]

出力

True

計算量のポイント

このアルゴリズムはリストを一度だけ走査するため、時間計算量は O(n)、追加で必要なメモリは定数 O(1) です。sorted() などで全体をソートしてから上位2つを取り出す方法（O(n log n)）よりも効率的です。

また、より簡潔に書きたい場合は、標準ライブラリの heapq モジュールを使って heapq.nlargest(2, nums) で上位2つの値を取得し、比較する方法もあります。用途や可読性の要件に応じて使い分けるとよいでしょう。