Easy

题目描述

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

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

示例 1：

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

示例 2：

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

提示：

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

解题思路

这道题要求判断数组中的最大元素是否至少是其他所有元素的两倍。

解法一：两次遍历

  1. 第一次遍历找到最大值及其索引
  2. 第二次遍历检查最大值是否至少是其他所有元素的两倍

解法二：一次遍历（推荐） 我们可以在一次遍历中同时找到最大值和第二大值：

  1. 维护最大值max1和第二大值max2及最大值的索引
  2. 遍历数组，更新这些值
  3. 最后检查max1 >= 2 * max2是否成立

一次遍历的方法更高效，因为它减少了对数组的访问次数。关键在于正确维护最大值和第二大值的关系：当遇到新的最大值时，原来的最大值变成第二大值；当遇到介于最大值和第二大值之间的数时，只更新第二大值。

代码实现

class Solution {
public:
    int dominantIndex(vector<int>& nums) {
        int max1 = -1, max2 = -1;
        int maxIndex = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > max1) {
                max2 = max1;
                max1 = nums[i];
                maxIndex = i;
            } else if (nums[i] > max2) {
                max2 = nums[i];
            }
        }
        
        return max1 >= 2 * max2 ? maxIndex : -1;
    }
};

class Solution:
    def dominantIndex(self, nums: List[int]) -> int:
        max1 = max2 = -1
        max_index = 0
        
        for i, num in enumerate(nums):
            if num > max1:
                max2 = max1
                max1 = num
                max_index = i
            elif num > max2:
                max2 = num
        
        return max_index if max1 >= 2 * max2 else -1

public class Solution {
    public int DominantIndex(int[] nums) {
        int max1 = -1, max2 = -1;
        int maxIndex = 0;
        
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] > max1) {
                max2 = max1;
                max1 = nums[i];
                maxIndex = i;
            } else if (nums[i] > max2) {
                max2 = nums[i];
            }
        }
        
        return max1 >= 2 * max2 ? maxIndex : -1;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var dominantIndex = function(nums) {
    let max1 = -1, max2 = -1;
    let maxIndex = 0;
    
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] > max1) {
            max2 = max1;
            max1 = nums[i];
            maxIndex = i;
        } else if (nums[i] > max2) {
            max2 = nums[i];
        }
    }
    
    return max1 >= 2 * max2 ? maxIndex : -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
一次遍历O(n)O(1)
两次遍历O(n)O(1)

相关题目