C++でリストnumsから nums[i] < nums[k] < nums[j] を満たすトリプレットを見つけるプログラム

問題概要

数値のリスト nums が与えられたとき、i < j < k かつ nums[i] < nums[k] < nums[j] を同時に満たすトリプレット (i, j, k) が存在するかどうかを判定します。

たとえば、入力が nums = [2, 12, 1, 4, 4] の場合、出力は True になります。これは [2, 12, 4] という組み合わせが条件に一致しているためです(2 < 4 < 12)。

解法のアプローチ

この問題は、「接頭辞最小値(prefix minimum)配列」とスタックを組み合わせることで、O(n) の計算量で効率的に解くことができます。手順は以下の通りです。

• n := nums のサイズとします

• サイズ n の配列 left を定義します(left[i] は nums[0..i] の範囲における最小値)

• left[0] := nums[0]

• i = 1 から n - 1 まで順に、left[i] := min(nums[i], left[i - 1]) として更新します

• スタック st を定義します

• i = n - 1 から 1 まで逆順に以下を繰り返します:

  • x := left[i - 1](i より前の要素の最小値)

  • st が空でなく、st の先頭が x 以下である間、要素をポップし続けます

  • st が空でなく、x < nums[i] かつ nums[i] > st の先頭 が成り立つ場合は true を返します

  • nums[i] を st にプッシュします

• ループが完了したら false を返します

アルゴリズムのポイント

left 配列を使うことで「j より前に存在する最小値」を即座に参照でき、スタックには右側から見て条件候補となり得る大きな値だけが残ります。その結果、各位置において条件を満たす組み合わせが存在するかを高速に判定できます。

実装例(C++)

理解を深めるために、以下の実装をご覧ください。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool solve(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n);
        left[0] = nums[0];
        for (int i = 1; i < n; i++) {
            left[i] = min(nums[i], left[i - 1]);
        }
        stack<int> st;
        for (int i = n - 1; i >= 1; i--) {
            int x = left[i - 1];
            while (!st.empty() && st.top() <= x)
                st.pop();
            if (!st.empty() && x < nums[i] && nums[i] > st.top())
                return true;
            st.push(nums[i]);
        }
        return false;
    }
};
bool solve(vector<int>& nums) {
    return (new Solution())->solve(nums);
}
int main(){
    vector<int> v = {2, 12, 1, 4, 4};
    cout << solve(v);
}

入力

{2, 12, 1, 4, 4}

出力

1