정수 배열 A가 있다고 가정하고 각 정수 A[i]에 대해 x =-K 또는 x =K를 선택하고 A[i]에 x를 추가해야 합니다(한 번만). 따라서 이 과정 후에 배열 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 - 최소)
-
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#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