Khoảng thời gian dài nhất chứa một số trong C ++

Giả sử chúng ta có một danh sách các số nguyên riêng biệt được gọi là nums. Chúng ta phải tìm kích thước của khoảng lớn nhất (bao gồm) [bắt đầu, kết thúc] sao cho nó chứa nhiều nhất một số tính bằng nums.

Vì vậy, nếu đầu vào là nums =[10, 6, 20], thì đầu ra sẽ là 99990, vì khoảng lớn nhất là [11, 100000], khoảng này chỉ chứa 20.

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -

• ret:=-inf

• end:=100000

• trước:=1

• sắp xếp số mảng

• n:=kích thước của nums

• để khởi tạo i:=0, khi tôi

  • nếu tôi + 1

    • cao:=nums [i + 1] - 1

  • Nếu không

    • cao:=end

  • nếu tôi - 1> =0, thì -

    • thấp:=trước + 1

  • Nếu không

    • thấp:=trước

  • trước:=nums [i]

  • ret:=tối đa của high - low + 1 và ret

• trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

{10, 6, 20}

Đầu ra

99990