C++의 최대 간격

<시간/>

정렬되지 않은 배열이 있다고 가정합니다. 정렬된 형식에서 연속 요소 간의 최대 차이를 찾아야 합니다. 배열에 2개 미만의 요소가 포함되어 있으면 0을 반환합니다. 따라서 배열이 [12,3,9,1,17]과 같으면 출력은 6이 됩니다. 정렬된 배열은 [1,3,9,12,17]이므로 5는 다음과 같이 최대 차이가 됩니다. 3과 9의 차이는 6입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

minVal :=inf, maxCal :=-inf
n :=숫자 크기
n <2이면 0을 반환합니다.
0 ~ n – 1 −
범위의 i에 대해
- minVal :=nums[i] 및 minVal의 최소값
- maxVal :=nums[i] 및 maxVal의 최대값
갭:=maxVal – minVal / n – 1의 셀링
n – 1 크기의 bucketMax라는 배열을 하나 만들고 –inf
로 채웁니다.
n – 1 크기의 bucketMin이라는 배열 하나를 만들고 이를 inf
로 채웁니다.
0 ~ n – 1 −
범위의 i에 대해
- x :=숫자[i]
- x =minVal 또는 x =maxVal이면 다음 부분을 건너뛰고 다음 반복으로 이동합니다.
- idx :=(nums[i] – minVal) / 간격.
- bucketMax[idx] :=bucketMax[idx] 및 nums[i]의 최대값
- bucketMin[idx] :=bucketMin[idx] 및 nums[i]의 최소값
렛 :=0
이전 :=minVal
0 ~ n – 1 범위의 i에 대해
- bucketMax[i] =-inf 및 bucketMin[i] =inf이면 다음 부분을 건너뛰고 다음 반복으로 이동합니다.
- ret :=ret 및 bucketMin[i]의 최대값 – 이전
- 이전 :=버킷맥스[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]