C++で1つの数値だけを含む最長区間を求めるアルゴリズム

問題概要

相異なる整数のリスト nums が与えられます。この中から、リスト内の数値を最大1つしか含まない区間 [start, end](両端を含む)のうち、最も長いもののサイズを求めましょう。

例えば、nums = [10, 6, 20] が入力された場合、出力は 99990 となります。これは、最も長い区間が [11, 100000] であり、この区間には 20 のみが含まれるためです。

解法のアプローチ

この問題は、配列をあらかじめソートしておき、各数値について「その数値のみを含む区間」を隣接する数値の位置から求めることで効率よく解けます。手順は以下の通りです。

• ret := −inf(答えを保持する変数)
• end := 100000(探索範囲の上限)
• prev := 1(直前の数値を保持する変数)
• 配列 nums をソートする
• n := nums のサイズ
• i := 0 から nums のサイズ未満の間、i を1ずつ増やしながら次を繰り返す
  • i + 1 < n の場合:high := nums[i + 1] − 1
  • そうでなければ:high := end
  • i − 1 ≥ 0 の場合:low := prev + 1
  • そうでなければ:low := prev
  • prev := nums[i]
  • ret := max(high − low + 1, ret)
• ret を返す

アルゴリズムのポイント

ソート後の各要素に対して、「前の要素 + 1」から「次の要素 − 1」までの範囲を見ることで、その要素だけを含む区間の長さを正確に計算できます。先頭の要素では始点を 1、末尾の要素では終点を 100000 とすることで、探索範囲の両端にも対応します。各区間の長さは high − low + 1 で表され、その最大値が最終的な答えとなります。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int> &nums) {
      int ret = INT_MIN;
      int end = 100000;
      int prev = 1;
      sort(nums.begin(), nums.end());
      int n = nums.size();
      int low, high;
      for (int i = 0; i < nums.size(); i++) {
         if (i + 1 < n) {
            high = nums[i + 1] - 1;
         } else
            high = end;
         if (i - 1 >= 0) {
            low = prev + 1;
         } else
            low = prev;
         prev = nums[i];
         ret = max(high - low + 1, ret);
      }
      return ret;
   }
};
main() {
   Solution ob;
   vector<int> v = {10, 6, 20};
   cout << (ob.solve(v));
}

入力例

{10, 6, 20}

出力例

99990

計算量

ソートに O(n log n)、その後の線形走査に O(n) の時間がかかるため、全体の計算量は O(n log n) となります。追加のメモリ使用量もごくわずかで、非常に効率的な解法です。