ช่วงเวลาที่ยาวที่สุดที่มีหนึ่งหมายเลขใน C ++

สมมติว่าเรามีรายการจำนวนเต็มเฉพาะที่เรียกว่า nums เราต้องหาขนาดของช่วงที่ใหญ่ที่สุด (รวม) [เริ่ม, สิ้นสุด] เพื่อให้มีตัวเลขเป็น num ได้ไม่เกินหนึ่งตัว

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[10, 6, 20] เอาต์พุตจะเป็น 99990 เนื่องจากช่วงที่ใหญ่ที่สุดคือ [11, 100000] จะมีเพียง 20 รายการเท่านั้น

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

• ret :=-inf

• จบ :=100000

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

• จัดเรียงตัวเลขอาร์เรย์

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

• สำหรับการเริ่มต้น i :=0 เมื่อ i <ขนาดของ nums ให้อัปเดต (เพิ่ม i ขึ้น 1) ให้ทำ -

  • ถ้า i + 1

    • สูง :=nums[i + 1] - 1

  • มิฉะนั้น

    • สูง :=จบ

  • ถ้า i - 1>=0 แล้ว −

    • ต่ำ :=ก่อนหน้า + 1

  • มิฉะนั้น

    • ต่ำ :=ก่อนหน้า

  • ก่อนหน้า :=nums[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}

ผลลัพธ์

99990