747. 至少是其他数字两倍的最大数

题目描述：

给你一个整数数组 nums ，其中总是存在 唯一的 一个最大整数 。

请你找出数组中的最大元素并检查它是否 至少是数组中每个其他数字的两倍 。如果是，则返回 最大元素的下标 ，否则返回 -1 。

示例 1：

输入：nums = [3,6,1,0]
输出：1
解释：6 是最大的整数，对于数组中的其他整数，6 至少是数组中其他元素的两倍。6 的下标是 1 ，所以返回 1 。

示例 2：

输入：nums = [1,2,3,4]
输出：-1
解释：4 没有超过 3 的两倍大，所以返回 -1 。

示例 3：

输入：nums = [1]
输出：0
解释：因为不存在其他数字，所以认为现有数字 1 至少是其他数字的两倍。

提示：

• 2 <= nums.length <= 50
• 0 <= nums[i] <= 100
• nums 中的最大元素是唯一的

---

解题分析及思路：

方法一：两次遍历数组

思路：

本题可以通过两次遍历数组的方法解决：

第一遍遍历数组找到最大值，保存最大值所对应的下标

第二遍遍历数组对比最大值与其他值的关系

• 如果最大值是其他值的两倍以上，则返回最大值所对应的下标
• 否则返回-1

func dominantIndex(nums []int) int {
	max := 0
	for index := range nums {
		if nums[index] > nums[max] {
			max = index
		}
	}
	for index := range nums {
		if 2*nums[index] > nums[max] && max != index {
			return -1
		}
	}
	return max
}

复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:2.18 MB,击败了6.45% 的Go用户

方法二：一次遍历数组

思路：

本题也可以通过一次遍历数组的方法解决：

遍历数组，找到最大值和次大值，然后判断最大值是否是次大值的两倍以上，如果是则返回最大值所对应的下标，否则返回-1

func dominantIndex(nums []int) int {
	if len(nums) == 1 {
		return 0
	}
	max, second := 0, 0
	for index := range nums {
		if nums[index] > nums[max] {
			max, second = index, max
		} else if nums[index] > nums[second] || second == max {
			second = index
		}
	}
	if 2*nums[second] > nums[max] {
		return -1
	}
	return max
}

复杂度：

• 时间复杂度：O(N)
• 空间复杂度：O(1)

执行结果：

• 执行耗时:0 ms,击败了100.00% 的Go用户
• 内存消耗:2.2 MB,击败了6.78% 的Go用户