JavaScriptで「ほぼ昇順」の配列を判定する方法

整数の配列が与えられたとき、その配列から1つ以下の要素を削除することで、厳密に増加する（狭義単調増加の）数列を作れるかどうかを判定する問題を考えてみましょう。

問題の定義

数列 a₀, a₁, ..., a_n が「厳密に増加する」とは、a₀ < a₁ < ... < a_n が成り立つことを指します。なお、要素が1つだけの数列も厳密に増加するものとみなします。

例1：false になるケース

sequence = [1, 3, 2, 1] の場合の出力は次のとおりです。

almostIncreasingSequence(sequence) = false

この配列では、どの要素を1つ削除しても厳密に増加する数列にはなりません。したがって false が返されます。

例2：true になるケース

sequence = [1, 3, 2] の場合の出力は次のとおりです。

almostIncreasingSequence(sequence) = true

この場合は 3 を削除すれば [1, 2] という厳密に増加する数列が得られます。あるいは 2 を削除して [1, 3] を得ることもできます。どちらでも条件を満たせるため、結果は true です。

実装コード

この問題は、配列を先頭から走査しながら「前の値より小さい・または等しい値」が出現した回数をカウントし、その回数が2回以上になった時点で不可能と判断するアルゴリズムで解けます。実装例は以下のとおりです。

const arr1 = [3, 5, 67, 98, 3];
const arr2 = [4, 3, 5, 67, 98, 3];

const almostIncreasingSequence = sequence => {
    let removed = 0;
    let i = 0;
    let prev = -Infinity;
    while (removed < 2 && i < sequence.length) {
        if (sequence[i] > prev) {
            // 昇順が維持されているので prev を更新
            prev = sequence[i];
        } else {
            // 順序違反：この要素を削除したものとしてカウント
            prev = Math.min(prev, sequence[i]);
            removed++;
        }
        i++;
    }
    return removed < 2;
};

console.log(almostIncreasingSequence(arr1));
console.log(almostIncreasingSequence(arr2));

アルゴリズムのポイント

• prev の初期値：-Infinity にすることで、最初の要素との比較が必ず成立します。
• 削除カウント：順序違反を見つけるたびに removed をインクリメントし、2回目の違反が見つかった時点でループを抜けます。
• Math.min の活用：削除対象の候補を切り替えるため、prev は現在の値との最小値に更新されます。これにより「直前の要素を削除するパターン」と「現在の要素を削除するパターン」の両方を暗黙的に扱えます。

出力結果

コンソールには次のように出力されます。

true
false

arr1 = [3, 5, 67, 98, 3] は末尾の 3 を1つ削除するだけで昇順になるため true。一方、arr2 = [4, 3, 5, 67, 98, 3] は冒頭の逆転と末尾の重複により2箇所の修正が必要となるため false となります。