Longest Interval Containing One Number in C++: หาช่วงใหญ่สุดที่มีตัวเลขจาก Array อย่างมาก 1 ตัว

กำหนด array nums ของจำนวนเต็มที่ไม่ซ้ำกัน หาขนาดของช่วง [start, end] ใหญ่สุด (inclusive) ที่มีตัวเลขจาก nums อยู่ในช่วง สูงสุด 1 ตัว

ตัวอย่าง: nums = [10, 6, 20] → Output: 99990

ช่วงใหญ่สุดคือ [11, 100000] มีแค่ 20 อยู่ในช่วง (สมมติขอบเขตบนคือ 100000)

วิธีแก้ปัญหา

เรียง nums
พิจารณาช่วงระหว่างตัวเลขที่ติดกัน และช่วงนอกสุด
สำหรับแต่ละ nums[i] คำนวณช่วงที่มีแค่ตัวนี้:
- low = (i>0) ? nums[i-1]+1 : 1
- high = (i+1
- ขนาด = high - low + 1
หาค่าสูงสุด

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(vector<int>& nums) {
        int ret = INT_MIN, end = 100000, prev = 1;
        sort(nums.begin(), nums.end());
        for(int i=0;i= 0) ? prev+1 : prev;
            prev = nums[i];
            ret = max(ret, high - low + 1);
        }
        return ret;
    }
};

int main() {
    Solution ob;
    vector<int> v = {10, 6, 20};
    cout << ob.solve(v);
}

Input

{10, 6, 20}