问题描述

给定一个整数数组 nums，其中总是存在唯一的一个最大整数。任务是找出数组中的最大元素，并检查它是否至少是数组中每个其他数字的两倍。如果是，则返回最大元素的下标；否则，返回 -1。

解题思路

这个问题可以通过两个主要步骤解决：

1. 寻找最大元素及其下标：首先，我们需要遍历数组以找到最大元素及其下标。

2. 验证条件：然后，我们需要检查这个最大元素是否至少是数组中其他每个元素的两倍。

 

算法实现

以下是使用 C++ 语言实现的算法：

#include <vector>public:int dominantIndex(std::vector<int>& nums) {int maxIndex = 0;int n = nums.size();// Step 1: Find the maximum element and its indexfor (int i = 1; i < n; i++) {if (nums[i] > nums[maxIndex]) {maxIndex = i;}}// Step 2: Check if the maximum element is at least twice of any other elementfor (int i = 0; i < n; i++) {if (i != maxIndex && nums[maxIndex] < nums[i] * 2) {return -1; // Condition not met}}return maxIndex; // Condition met, return the index of the maximum element}
};

代码分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。这是因为我们遍历数组两次：一次寻找最大元素，一次验证条件。

• 空间复杂度：O(1)，我们只使用了有限的额外空间。

结论

这个问题是一个典型的数组问题，它要求我们首先找到数组中的最大元素，然后进行条件验证。通过这个例子，我们可以看到，有时候解决问题的关键在于正确地分解问题并逐步解决每个子问题。