solution.h

/*
Code generated by https://github.com/goodstudyqaq/leetcode-local-tester
*/
#if __has_include("../utils/cpp/help.hpp")
#include "../utils/cpp/help.hpp"
#elif __has_include("../../utils/cpp/help.hpp")
#include "../../utils/cpp/help.hpp"
#else
#define debug(...) 42
#endif

typedef pair<int, int> pii;
class Solution {
   public:
    int maximumGap(vector<int>& nums) {
        if (nums.size() <= 1) {
            return 0;
        }
        int mx = *max_element(nums.begin(), nums.end());
        int mi = *min_element(nums.begin(), nums.end());

        if (mx == mi) return 0;

        int n = nums.size();
        int blank = max(1, (mx - mi) / (n - 1));

        int num = (mx - mi - 1) / blank + 1;

        vector<pii> V(num + 1, {1e9, -1e9});
        for (int i = 0; i < n; i++) {
            int tmp = (nums[i] - mi) / blank;
            V[tmp].first = min(V[tmp].first, nums[i]);
            V[tmp].second = max(V[tmp].second, nums[i]);
        }

        int before = -1;
        int ans = 0;
        for (int i = 0; i < num + 1; i++) {
            if (V[i].first != 1e9) {
                if (before != -1) {
                    ans = max(ans, V[i].first - V[before].second);
                }
                before = i;
            }
        }
        return ans;

    }
};