C++でリストを左右に分割できるか判定するアルゴリズム

問題の概要

整数のリスト nums が与えられたとき、このリストを2つの空でない部分リストに分割できるかどうかを判定します。ただし、左側の部分リストに含まれるすべての数値は、右側の部分リストに含まれるすべての数値よりも厳密に小さい必要があります。

例えば、入力が [6, 4, 3, 8, 10] の場合を見てみましょう。left = [6, 4, 3]、right = [8, 10] と分割すると、左側の最大値 6 は右側の最小値 8 より小さいため、出力は true（1）になります。

解決のアプローチ

この問題は、プレフィックス最大値（左側からの累積最大値）とサフィックス最小値（右側からの累積最小値）を事前に計算しておくことで、効率的に解くことができます。

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

• n を nums のサイズとする

• サイズ n の配列 left と right を定義する

• left[0] = nums[0]、right の末尾要素 = nums の末尾要素 として初期化する

• i = 1 から n - 1 までループ：
  left[i] = max(left[i - 1], nums[i])（インデックス i までの左側の最大値を記録）

• i = n - 2 から 0 まで逆順にループ：
  right[i] = min(right[i + 1], nums[i])（インデックス i 以降の右側の最小値を記録）

• i = 0 から n - 2 までループ：
  left[i] < right[i + 1] を満たす位置があれば true を返す

• どの分割位置でも条件を満たさなければ false を返す

計算量

• 時間計算量： O(n) — 各配列をそれぞれ一度ずつ走査するだけです
• 空間計算量： O(n) — 補助配列 left と right が必要です

C++ 実装例

それでは、理解を深めるために以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool solve(vector<int> &nums) {
        int n = nums.size();
        vector<int> right(n);
        vector<int> left(n);
        left[0] = nums[0];
        right.back() = nums.back();
        for (int i = 1; i < n; i++) {
            left[i] = max(left[i - 1], nums[i]);
        }
        for (int i = n - 2; i >= 0; i--) {
            right[i] = min(right[i + 1], nums[i]);
        }
        for (int i = 0; i < n - 1; i++) {
            if (left[i] < right[i + 1])
            return true;
        }
        return false;
    }
};
main() {
    Solution ob;
    vector<int> v = {6,4,3,8,10};
    cout << (ob.solve(v));
}

入力

{6,4,3,8,10}

出力

1

まとめ

この手法では、各分割位置における「左側の最大値」と「右側の最小値」を前処理で求めておくことで、全ての分割候補を線形時間でチェックできます。ナイーブな全探索では O(n²) かかるところを、O(n) まで高速化できるのがポイントです。