C++で解く「最小範囲 II」：±K の加算で最大値と最小値の差を最小化するアルゴリズム

問題の概要

整数の配列 A が与えられます。各要素 A[i] に対して、x = -K または x = K のどちらか一方を選び、その値を A[i] に加算します（各要素につき1回のみ）。この操作をすべての要素に適用すると、新しい配列 B が得られます。求めるのは、B の最大値と最小値の差として実現できる最小値です。

例として、入力が A = [0, 10]、K = 2 の場合を考えてみましょう。このとき B = [2, 8] となるため、出力は 6 になります。

解法のアプローチ

この問題は、以下の手順で解くことができます。

• ret := 0、n := 配列 A のサイズ と初期化する

• 配列 A を昇順にソートする

• ret := A の最後の要素 − A の最初の要素 とする（すべての要素に同じ符号を適用した場合の差）

• right := A の最後の要素 − K、left := A の最初の要素 + K とする

• i を 0 から n − 1 まで繰り返す

  • mx := max(A[i] + k, right)

  • mn := min(A[i + 1] − k, left)

  • ret := min(ret, mx − mn)

• ret を返す

アルゴリズムの考え方

配列をソートすると、最適な解では「ある境界位置より前の要素には +K を、後ろの要素には −K を適用する」という構造になります。ソート済みの配列で、小さい要素に −K を、大きい要素に +K を加えると差は広がる一方だからです。そこで、境界の位置をすべて試しながら、そのときの最大値（mx）と最小値（mn）の差を計算し、その最小値を求めればよいことになります。

C++ 実装例

以下に、実際の実装例を示します。

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int smallestRangeII(vector<int>& A, int k) {
      int ret = 0;
      int n = A.size();
      sort(A.begin(), A.end());
      ret = A[n - 1] - A[0];
      int mx, mn;
      int right = A[n - 1] - k;
      int left = A[0] + k;
      for(int i = 0; i < n - 1; i++){
         mx = max(A[i] + k, right);
         mn = min(A[i + 1] - k, left);
         ret = min(ret, mx - mn);
    }
    return ret;
   }
};
main(){
   vector<int> v = {0, 10};
   Solution ob;
   cout << (ob.smallestRangeII(v, 2));
}

入力

[0,10]
2

出力

6

計算量

ソートに O(n log n)、その後の走査に O(n) かかるため、全体の時間計算量は O(n log n) です。追加のメモリ使用量は O(1)（ソートを除く）と非常に効率的です。