ช่องว่างสูงสุดใน C++

สมมติว่าเรามีอาร์เรย์ที่ไม่ได้เรียงลำดับ เราต้องหาความแตกต่างสูงสุดระหว่างองค์ประกอบที่ต่อเนื่องกันในรูปแบบการเรียงลำดับ เราจะคืนค่า 0 หากอาร์เรย์มีองค์ประกอบน้อยกว่า 2 รายการ ดังนั้นหากอาร์เรย์เป็นเหมือน [12,3,9,1,17] ผลลัพธ์จะเป็น 6 เนื่องจากอาร์เรย์ที่จัดเรียงจะเป็น [1,3,9,12,17] ดังนั้น 5 จะเป็นผลต่างสูงสุดดังนี้ ความแตกต่างระหว่าง 3 และ 9 คือ 6.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• minVal :=inf, maxCal :=-inf

• n :=ขนาดของ nums

• ถ้า n <2 ให้คืนค่า 0;

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1 −

  • minVal :=นาทีของ nums[i] และ minVal

  • maxVal :=สูงสุดของ nums[i] และ maxVal

• gap :=celing ของ maxVal – minVal / n – 1

• สร้างหนึ่งอาร์เรย์ที่เรียกว่า bucketMax ขนาด n – 1 และเติมด้วย –inf

• สร้างอาร์เรย์หนึ่งชื่อ bucketMin ขนาด n – 1 และเติมด้วย inf

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1 −

  • x :=nums[i]

  • ถ้า x =minVal หรือ x =maxVal ให้ข้ามส่วนถัดไป ทำซ้ำต่อไป

  • idx :=(nums[i] – minVal) / gap.

  • bucketMax[idx] :=สูงสุดของ bucketMax[idx] และ nums[i]

  • bucketMin[idx] :=นาทีของ bucketMin[idx] และ nums[i]

• ยกเลิก :=0

• ก่อนหน้า :=minVal

• สำหรับฉันอยู่ในช่วง 0 ถึง n – 1

  • ถ้า bucketMax[i] =-inf และ bucketMin[i] =inf ให้ข้ามส่วนถัดไป ทำซ้ำต่อไป

  • ret :=สูงสุดของ ret และ bucketMin[i] – ก่อนหน้า

  • ก่อนหน้า :=bucketMax[i]

• คืนค่าสูงสุดของ ret, maxVal - ก่อนหน้า

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
   public:
   int maximumGap(vector<int>& nums) {
      lli minVal = INT_MAX;
      lli maxVal = INT_MIN;
      int n = nums.size();
      if(n < 2) return 0;
      for(int i = 0; i < n; i++){
         minVal = min((lli)nums[i], minVal);
         maxVal = max((lli)nums[i], maxVal);
      }
      int gap = ceil((double)(maxVal - minVal) / (double)(n - 1));
      vector <int> bucketMax(n - 1, INT_MIN);
      vector <int> bucketMin(n - 1, INT_MAX);
      for(int i = 0; i < n; i++){
         int x = nums[i];
         if(x == minVal || x == maxVal) continue;
         int idx = (nums[i] - minVal) / gap;
         bucketMax[idx] = max(bucketMax[idx], nums[i]);
         bucketMin[idx] = min(bucketMin[idx], nums[i]);
      }
      lli ret = 0;
      lli prev = minVal;
      for(int i = 0; i < n - 1; i++){
         if(bucketMax[i] == INT_MIN && bucketMin[i] == INT_MAX) continue;
         ret = max(ret, bucketMin[i] - prev);
         prev = bucketMax[i];
      }
      return max(ret, maxVal - prev);
   }
};
main(){
   Solution ob;
   vector<int> v = {12,3,9,1,17};
   cout << (ob.maximumGap(v));
}

อินพุต

[12,3,9,1,17]

ผลลัพธ์

6