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

Cho mảng nums các số nguyên khác nhau. Tìm độ dài lớn nhất của khoảng [start, end] (trong phạm vi 1..100000) sao cho khoảng đó chứa tối đa một số trong nums.

Ví dụ: nums = [10, 6, 20] → 99990 (khoảng [11, 100000] chỉ chứa 20).

Giải thuật: Sắp xếp nums. Với mỗi số nums[i], tính khoảng cách đến số kế tiếp (hoặc 100000) và số trước (hoặc 1). Lấy max của high - low + 1.

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();
        for (int i = 0; i < n; i++) {
            int high = (i + 1 < n) ? nums[i+1] - 1 : end;
            int low = (i - 1 >= 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));
}

Đầu vào

{10, 6, 20}

Đầu ra

99990