C++の最小範囲II

整数の配列Aがあるとします。整数A[i]ごとに、x=-Kまたはx=Kのいずれかを選択し、xをA [i]に追加する必要があります（1回のみ）。したがって、このプロセスの後に、配列Bができます。Bの最大値とBの最小値の間の可能な限り最小の差を見つける必要があります。したがって、入力がA =[0,10]、K =2の場合、 B =[2,8]であるため、出力は6になります。

これを解決するには、次の手順に従います-

• set ret：=0、n：=配列Aのサイズ

• 配列Aを並べ替える

• set ret：=Aの最後の要素–Aの最初の要素

• 右：=A – Kの最後の要素と左：=A+kの最初の要素

• 0からn–1の範囲のiの場合

  • mx：=A [i]+kの最大値と右

  • mn：=A [i + 1]の最小値–kおよび左

  • ret：=retの最小値および（mx-分）

• retを返す

理解を深めるために、次の実装を見てみましょう-

例

#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