题目描述
Given an unsorted array, find the maximum difference between the successive elements in its sorted form.
Return 0 if the array contains less than 2 elements.
题目大意
给定一个乱序数组，要求找到该数组在有序情况下相邻两数字最大差值。
要求：在O(n)时间复杂度以及空间复杂度内完成。
示例
E1
Input: [3,6,9,1] Output: 3
E2
Input: [10] Output: 0
解题思路
感谢LeetCode@zkfairytale的代码得到效率更好的代码。
由于最终结果的差值大小一定 >= bucket_size = (max - min) / (n - 1)，其中max为数组中最大值，min为最小值，n为数组元素个数，可将所有数字分配在各个大小为bucket_size的桶中。由上述条件可知，最终结果一定大于等于bucket_size，因此可以遍历两个相邻bucket之间的最大值与最小值来获得可能的最大的差值。
复杂度分析
时间复杂度：O(log(n))
空间复杂度：O(1)
代码
class Solution {
public:
int findPeakElement(vector<int>& nums) {
return solve(nums, 0, nums.size() - 1);
}
//二分搜索
int solve(vector<int>& nums, int low, int high) {
if(low == high)
return low;
int mid1 = (low + high) / 2;
int mid2 = mid1 + 1;
//寻找两个较大的数字之间的数字的位置
if(nums[mid1] > nums[mid2])
return solve(nums, low, mid1);
else
return solve(nums, mid2, high);
}
};
原文：https://www.cnblogs.com/heyn1/p/10949720.html