สมมติว่าเรามีอาร์เรย์ A ของจำนวนเต็ม สำหรับแต่ละจำนวนเต็ม A[i] เราต้องเลือก x =-K หรือ x =K และเพิ่ม x ให้กับ A[i] (เพียงครั้งเดียว) หลังจากกระบวนการนี้ เรามีอาร์เรย์ B เราต้องหาความแตกต่างที่น้อยที่สุดที่เป็นไปได้ระหว่างค่าสูงสุดของ B และค่าต่ำสุดของ B ดังนั้นหากอินพุตคือ A =[0,10], K =2 แล้ว ผลลัพธ์จะเป็น 6 เนื่องจาก B =[2,8].
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
set ret :=0, n :=ขนาดของอาร์เรย์ A
-
จัดเรียงอาร์เรย์ A
-
set ret :=องค์ประกอบสุดท้ายของ A – องค์ประกอบแรกของ A
-
ขวา :=องค์ประกอบสุดท้ายของ A – K และซ้าย :=องค์ประกอบแรกของ A + k
-
สำหรับฉันอยู่ในช่วง 0 ถึง n – 1
-
mx :=สูงสุดของ A[i] + k และขวา
-
mn :=นาทีของ A[i + 1] – k และซ้าย
-
ret :=นาทีของ ret และ (mx - min)
-
-
รีเทิร์น
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#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
