Pythonで非減少配列を判定する方法：最大1要素の変更で解くアルゴリズム

問題の概要

n個の整数からなる配列が与えられます。求めたいのは、最大1つの要素だけを変更して、その配列を「非減少配列（non-decreasing array）」にできるかどうかの判定です。

ここで非減少配列とは、すべてのインデックス i（1 ≤ i < n）に対して array[i] <= array[i + 1] が成り立つ配列を指します。

例として、配列が [4,2,3] の場合を考えてみましょう。先頭の 4 を 1 に変更すれば [1,2,3] となり、非減少配列へ変換できるため、答えは True になります。

解法のアプローチ

この問題は、配列を左から順に走査し、「降順になっている箇所（arr[i] > arr[i + 1]）」の出現回数を数えることで解けます。修正済みを示すフラグを用意し、違反が2回以上見つかった時点で False を返すのがポイントです。

具体的な手順は以下のとおりです。

• 配列の要素数が2以下なら、常に True を返す
• フラグ ans を False で初期化する
• i を 0 から（要素数 − 2）までループする
  • arr[i] > arr[i + 1] の場合
    • ans がすでに True なら False を返す。そうでなければ ans を True に更新する
    • i > 0 の場合はさらに、arr[i - 1] > arr[i + 1] であれば arr[i + 1] := arr[i] とする
• ループが完了したら True を返す

Pythonでの実装例

以下の実装例を見ると、処理の流れがより明確になります。

class Solution(object):
    def checkPossibility(self, nums):
        if len(nums) <= 2:
            return True
        ans = False
        for i in range(len(nums) - 1):
            if nums[i] > nums[i + 1]:
                if ans:
                    return False
                else:
                    ans = True
                if i > 0:
                    if nums[i - 1] > nums[i + 1]:
                        nums[i + 1] = nums[i]
        return True

ob1 = Solution()
print(ob1.checkPossibility([4, 2, 3, 5]))

入力

[4,2,3,5]

出力

True

アルゴリズムのポイント

降順のペア（nums[i] > nums[i + 1]）を発見したときは、nums[i] を下げるか、nums[i + 1] を上げるかのどちらかを選択できます。直前の要素 nums[i - 1] が nums[i + 1] より大きい場合、nums[i] を下げても非減少の条件が崩れてしまうため、代わりに nums[i + 1] を nums[i] に引き上げるのが安全です。

このアルゴリズムは配列を一度だけ走査するため計算量は O(n)、追加の記憶領域も定数個のみで O(1) と非常に効率的です。