题解
求连续极大差，要求O(n)。 利用鸽笼原理。 先给出一个前置条件，即最大差不小于(max-min)/(n-1)，为什么？ 想象一个阶梯，阶梯间的最大高度差和平均高度差的关系。 有了这个差值，我们可以把原数组依据其所在区间分为n-1个桶。 显然落于同一个桶内的数我们不关心，我们只关心相邻桶间的数。 n个数，除了最大最小之外，还有n-2个数，入n-1个桶，至少有一个桶没有数。 答案就是跨越这个空桶(可能不止一个)的两边桶间 最大数的差值。
ps：具体实现的时候每个桶内只存区间内最大最小值。这样相邻的好计算。
Code
int maximumGap(vector
<int>& nums
) {
if(nums
.empty()||nums
.size()<2) return 0;
int n
=nums
.size();
int _max
,_min
;
_max
=_min
=nums
[0];
for(int i
:nums
){
_max
=max(_max
,i
);
_min
=min(_min
,i
);
}
if(_max
==_min
) return 0;
double gap
= (double)(_max
-_min
)/(n
-1);
vector
<int> g_min(n
,INT_MAX
);
vector
<int> g_max(n
,INT_MIN
);
for(int num
:nums
){
int idx
= (num
-_min
)/gap
;
g_min
[idx
]=min(g_min
[idx
],num
);
g_max
[idx
]=max(g_max
[idx
],num
);
}
int res
=0,pre
=g_max
[0];
for(int i
=1;i
<n
;i
++){
if(g_min
[i
]==INT_MAX
&& g_max
[i
]==INT_MIN
) continue;
res
=max(res
,g_min
[i
]-pre
);
pre
=g_max
[i
];
}
return res
;
}
