C++에서 하나의 숫자를 포함하는 가장 긴 간격

nums라고 하는 고유한 정수 목록이 있다고 가정합니다. 최대 하나의 숫자를 포함하도록 가장 큰 간격(포함) [start, end]의 크기를 찾아야 합니다.

따라서 입력이 nums =[10, 6, 20]과 같으면 출력은 99990이 됩니다. 가장 큰 간격은 [11, 100000]이므로 여기에는 20만 포함됩니다.

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

ret :=-inf
끝 :=100000
이전 :=1
배열 번호 정렬
n :=숫자 크기
initialize i :=0의 경우, i <숫자의 크기일 때 업데이트(i를 1만큼 증가), 수행 -
- i + 1
  - 높음 :=숫자[i + 1] - 1
- 그렇지 않으면
  - 높음 :=끝
- i - 1>=0이면 -
  - 낮음 :=이전 + 1
- 그렇지 않으면
  - 낮음 :=이전
- 이전 :=숫자[i]
- ret :=최고 - 최저 + 1 및 ret의 최대값
리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int> &nums) {
      int ret = INT_MIN;
      int end = 100000;
      int prev = 1;
      sort(nums.begin(), nums.end());
      int n = nums.size();
      int low, high;
      for (int i = 0; i < nums.size(); i++) {
         if (i + 1 < n) {
            high = nums[i + 1] - 1;
         } else
         high = end;
         if (i - 1 >= 0) {
            low = prev + 1;
         } else
         low = prev;
         prev = nums[i];
         ret = max(high - low + 1, ret);
      }
      return ret;
   }
};
main() {
   Solution ob;
   vector<int> v = {10, 6, 20};
   cout << (ob.solve(v));
}

입력

{10, 6, 20}