LeetCode164 最大间距

发表于 | 分类于 |
字数统计: 245 | 阅读时长 ≈ 1

链接: https://leetcode.cn/problems/maximum-gap/

题意

给定一个无序的数组 nums，返回 数组在排序之后，相邻元素之间最大的差值 。如果数组元素个数小于 2，则返回 0 。
要求O(n)时间和空间复杂度

解法

桶排序
写错一个取最小值
调了一个多小时
自闭了
不想说话 看代码吧

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
typedef long long ll;
class Solution {
public:
    int pushToBucket(ll maxv, ll minv, ll value, ll buckets) {
        return int((value - minv) * buckets / (maxv - minv));
    }
    int maximumGap(vector<int>& nums) {
        int n = nums.size();
        int maxv = INT_MIN, minv = INT_MAX;
        for (int i: nums) {
            maxv = max(i, maxv);
            minv = min(i, minv);
        }
        if (maxv == minv) return 0;
        vector<int> bmax(n + 1, INT_MIN), bmin(n + 1, INT_MAX), hasNum(n + 1);
        for (int i: nums) {
            int idx = pushToBucket(maxv, minv, i, n);
            bmax[idx] = max(bmax[idx], i);
            bmin[idx] = min(bmin[idx], i);
            hasNum[idx] = 1;
        }
        int ans = 0, premax = -1;
        for (int i = 0; i <= n; i++) {
            if (hasNum[i]) {
                if (premax != -1) {
                    ans = max(ans, bmin[i] - premax);
                }
                premax = bmax[i];
            }
        }
        return ans;

    }
};