链表中储存n个数,找出相差最大的两个数
时间: 2023-05-11 18:03:52 浏览: 53
可以使用双指针法,先将链表排序,然后用两个指针分别指向链表的头和尾,计算它们之间的差值,找出最大的差值即可。以下是示例代码:
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
int maxGap(ListNode* head) {
if (!head || !head->next) return 0;
int n = 0, maxVal = INT_MIN, minVal = INT_MAX;
for (ListNode* p = head; p; p = p->next) {
n++;
maxVal = max(maxVal, p->val);
minVal = min(minVal, p->val);
}
int gap = maxVal - minVal;
if (gap == 0) return 0;
vector<ListNode*> buckets(n + 1, nullptr);
for (ListNode* p = head; p; p = p->next) {
int i = (long long)(p->val - minVal) * n / gap;
if (!buckets[i]) buckets[i] = new ListNode(p->val);
else {
ListNode* q = buckets[i];
while (q->next) q = q->next;
q->next = new ListNode(p->val);
}
}
int prevMax = maxVal;
for (int i = n; i >= 0; i--) {
if (!buckets[i]) continue;
int curMin = INT_MAX;
ListNode* p = buckets[i];
while (p) {
curMin = min(curMin, p->val);
p = p->next;
}
gap = max(gap, prevMax - curMin);
prevMax = max(prevMax, maxVal);
}
return gap;
}
注意:这段代码使用了桶排序的思想,时间复杂度为 O(n),空间复杂度为 O(n)。