164.最大间距

/*
 * @lc app=leetcode.cn id=164 lang=typescript
 *
 * [164] 最大间距
 */

// @lc code=start
function maximumGap(nums: number[]): number {
	if (nums.length <= 2) return 0;
	// 归并排序
	let sortArr = mergeSort(nums);

	// 最大差值
	let maxDiff: number = 0;
	for (let i = 0; i < sortArr.length - 1; i++) {
		if (Math.abs(sortArr[i + 1] - sortArr[i]) > maxDiff) {
			maxDiff = Math.abs(sortArr[i + 1] - sortArr[i]);
		}
	}

	console.log(maxDiff);

	return maxDiff;
}

maximumGap([3, 6, 9, 1]);

// 归并算法
function mergeSort(nums: number[]): number[] {
	if (nums.length <= 1) return nums;

	let mid = Math.floor(nums.length / 2);
	let left = nums.slice(0, mid);
	let right = nums.slice(mid);

	return merge(mergeSort(left), mergeSort(right));
}

function merge(left: number[], right: number[]): number[] {
	let result: number[] = [];
	let leftIndex = 0;
	let rightIndex = 0;

	// 遍历数组
	while (leftIndex < left.length && rightIndex < right.length) {
		if (left[leftIndex] < right[rightIndex]) {
			result.push(left[leftIndex]);
			leftIndex++;
		} else {
			result.push(right[rightIndex]);
			rightIndex++;
		}
	}

	return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
// @lc code=end