JavaScriptで配列が「ほぼ増加列」（almostIncreasingSequence）かどうかを判定する方法

問題の概要

整数の配列として与えられる数列について、最大1つの要素を取り除くだけで厳密に増加する数列（隣り合う要素がすべて a₀ < a₁ < … < aₙ を満たす並び）にできるかどうかを判定します。

なお、要素が1つだけの数列も厳密に増加しているものとみなします。

具体例

例1：false を返すケース

sequence = [1, 3, 2, 1] の場合の出力：

almostIncreasingSequence(sequence) = false

この配列では、どの要素を1つだけ削除しても厳密に増加する数列を作ることができません。

例2：true を返すケース

sequence = [1, 3, 2] の場合の出力：

almostIncreasingSequence(sequence) = true

3 を削除すれば [1, 2] という厳密に増加する数列が得られます。あるいは 2 を削除して [1, 3] としても同じ結果になります。

実装コード

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 = sequence[i];
        } else {
            prev = Math.min(prev, sequence[i]);
            removed++;
        }
        i++;
    }
    return removed < 2;
};

console.log(almostIncreasingSequence(arr1)); // true
console.log(almostIncreasingSequence(arr2)); // false

コードの解説

このアルゴリズムは、配列を先頭から順に1回走査するだけで判定できる効率的な手法です。

• removed：「削除が必要」になった箇所の個数をカウントします。ループ条件 removed < 2 により、違反が2箇所見つかった時点で即座に走査を打ち切り、無駄な処理を省きます。
• prev：直前の値を保持する変数です。初期値を -Infinity にしておくことで、最初の要素は必ず受理されます。
• 現在の要素 sequence[i] が prev より大きければ、まだ増加関係が保たれているため prev を更新して先へ進みます。
• prev 以下だった場合は、どちらか一方を「削除した」ものとみなして removed を +1 します。このとき prev = Math.min(prev, sequence[i]) とすることで、「前の値を消すパターン」「今の値を消すパターン」の両方に柔軟に対応できます。

最終的に removed < 2 を返すことで、「削除は高々1回で済んだか」を判定します。時間計算量 O(n)・空間計算量 O(1) と、非常に効率的な解法です。

実行結果

true
false

arr1 = [3, 5, 67, 98, 3] は末尾の 3 を1つ削除すれば [3, 5, 67, 98] という増加列になるため true。
一方 arr2 = [4, 3, 5, 67, 98, 3] は先頭付近（4 → 3）と末尾（98 → 3）の2箇所で減少が発生しているため、1つの削除では対応できず false となります。