C++で最大ギャップを求める方法｜バケット法によるO(n)アルゴリズムの解説

問題の概要

ソートされていない整数の配列が与えられます。この配列を昇順に並べ替えたときの、隣接する要素同士の差の最大値を求めてください。ただし、配列の要素数が2未満の場合は 0 を返します。

例として、配列が [12, 3, 9, 1, 17] の場合を考えてみましょう。ソートすると [1, 3, 9, 12, 17] となり、隣接要素間の差は「2, 6, 3, 5」になります。この中で最も大きいのは 3 と 9 の差である 6 なので、答えは 6 となります。

解法の考え方(バケット法)

実際に配列をソートしてから差を計算しても解けますが、その場合の計算量は O(n log n) です。ここではバケット(bucket)分割を利用することで、時間計算量 O(n)・空間計算量 O(n) で効率的に解く方法を紹介します。

鳩の巣原理より、最大の差は必ず「異なるバケットの間」で発生することが保証されます。そのため、各バケット内の最小値と、その前に現れた値との差だけを調べればよいのがこの手法のポイントです。具体的な手順は以下の通りです。

• minVal := 正の無限大、maxVal := 負の無限大 で初期化する

• n := 配列 nums のサイズとする

• n < 2 の場合は 0 を返す

• i を 0 ～ n-1 までループ:

  • minVal := nums[i] と minVal の小さい方

  • maxVal := nums[i] と maxVal の大きい方

• gap := (maxVal - minVal) ÷ (n - 1) の切り上げ値

• サイズ n - 1 の配列 bucketMax を作成し、すべて負の無限大で初期化する

• サイズ n - 1 の配列 bucketMin を作成し、すべて正の無限大で初期化する

• i を 0 ～ n-1 までループ:

  • x := nums[i]

  • x が minVal または maxVal と一致する場合は何もせず次の反復へ

  • idx := (nums[i] - minVal) ÷ gap

  • bucketMax[idx] := bucketMax[idx] と nums[i] の大きい方

  • bucketMin[idx] := bucketMin[idx] と nums[i] の小さい方

• ret := 0、prev := minVal とする

• i を 0 ～ n-1 までループ:

  • bucketMax[i] が負の無限大 かつ bucketMin[i] が正の無限大(空のバケット)ならスキップして次へ

  • ret := ret と bucketMin[i] - prev の大きい方

  • prev := bucketMax[i]

• ret と maxVal - prev のうち大きい方を返す

C++による実装例

理解を深めるために、上記の手順を実際のコードで確認してみましょう。

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
    public:
    int maximumGap(vector<int>& nums) {
       lli minVal = INT_MAX;
       lli maxVal = INT_MIN;
       int n = nums.size();
       if(n < 2) return 0;
       for(int i = 0; i < n; i++){
          minVal = min((lli)nums[i], minVal);
          maxVal = max((lli)nums[i], maxVal);
       }
       int gap = ceil((double)(maxVal - minVal) / (double)(n - 1));
       vector <int> bucketMax(n - 1, INT_MIN);
       vector <int> bucketMin(n - 1, INT_MAX);
       for(int i = 0; i < n; i++){
          int x = nums[i];
          if(x == minVal || x == maxVal) continue;
          int idx = (nums[i] - minVal) / gap;
          bucketMax[idx] = max(bucketMax[idx], nums[i]);
          bucketMin[idx] = min(bucketMin[idx], nums[i]);
       }
       lli ret = 0;
       lli prev = minVal;
       for(int i = 0; i < n - 1; i++){
          if(bucketMax[i] == INT_MIN && bucketMin[i] == INT_MAX) continue;
          ret = max(ret, bucketMin[i] - prev);
          prev = bucketMax[i];
       }
       return max(ret, maxVal - prev);
   }
};
main(){
    Solution ob;
    vector<int> v = {12,3,9,1,17};
    cout << (ob.maximumGap(v));
}

入力例

[12,3,9,1,17]

出力例

6

計算量について

このアルゴリズムは配列を数回走査するだけでよく、比較ベースのソートを行わないため、全体の時間計算量は O(n) です。バケット用の配列が必要となるため空間計算量は O(n) となります。要素数の多い大規模な配列に対して、ソート前提の O(n log n) のアプローチよりも高速に動作できるのが大きな特徴です。