增量元素之间的最大差值

难度: Easy

给你一个下标从 0 开始的整数数组 nums ，该数组的大小为 n ，请你计算 nums[j] - nums[i] 能求得的 最大差值 ，其中 0 <= i < j < n 且 nums[i] < nums[j] 。

返回 最大差值 。如果不存在满足要求的 i 和 j ，返回 -1 。

示例 1：

输入：nums = [7,1,5,4]
输出：4
解释：
最大差值出现在 i = 1 且 j = 2 时，nums[j] - nums[i] = 5 - 1 = 4 。
注意，尽管 i = 1 且 j = 0 时 ，nums[j] - nums[i] = 7 - 1 = 6 > 4 ，但 i > j 不满足题面要求，所以 6 不是有效的答案。

示例 2：

输入：nums = [9,4,3,2]
输出：-1
解释：
不存在同时满足 i < j 和 nums[i] < nums[j] 这两个条件的 i, j 组合。

示例 3：

输入：nums = [1,5,2,10]
输出：9
解释：
最大差值出现在 i = 0 且 j = 3 时，nums[j] - nums[i] = 10 - 1 = 9 。

提示：

n == nums.length
2 <= n <= 1000
1 <= nums[i] <= 10⁹

Submission

运行时间: 26 ms

内存: 16.1 MB

class Solution:
    def maximumDifference(self, nums: List[int]) -> int:
        ans = 0
        cnt = nums[0]
        for num in nums:
            cnt = min(cnt, num)
            ans = max(num - cnt, ans)
        if ans == 0:
            return -1
        return ans

Explain

该题解采用一次遍历的方法来解决问题。首先，定义一个变量 `cnt`，用于存储目前为止遇到的最小值。然后，遍历整个数组，对每个元素，更新 `cnt` 为当前元素和 `cnt` 中较小的一个，同时计算当前元素与 `cnt` 的差值，并更新最大差值 `ans`。遍历完成后，如果 `ans` 仍为0，说明没有找到满足条件的 `i` 和 `j`，因此返回 -1。否则，返回 `ans`，即最大差值。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def maximumDifference(self, nums: List[int]) -> int:
        ans = 0  # 初始化最大差值为0
        cnt = nums[0]  # 初始化cnt为数组的第一个元素，记录目前为止的最小值
        for num in nums:  # 遍历数组中的每个元素
            cnt = min(cnt, num)  # 更新cnt为当前元素和cnt中的较小值
            ans = max(num - cnt, ans)  # 更新最大差值ans
        if ans == 0:  # 如果ans为0，说明没有找到符合条件的i和j
            return -1  # 返回-1
        return ans  # 返回最大差值

Explore

在算法中初始化 `ans` 为0而不是负无穷大，是因为题目要求的是最大差值，且差值非负（即 `num[j] - num[i]`，其中 `j > i`）。如果初始化为负无穷大，那么任何正的差值都会更新这个变量，但如果数组中没有任何两个元素满足 `j > i`，即数组完全没有增量元素，按照题目要求应返回 -1。将 `ans` 初始化为0可以直接使用 `ans` 的值来判断是否存在有效的差值，如果遍历结束后 `ans` 仍为0，则说明数组中没有任何元素比先前的元素大，直接返回-1即可。

如果数组 `nums` 是单调递减的，每个元素比前一个小或相等，那么 `num - cnt` 的结果始终不会大于0（因为 `cnt` 是迄今为止遇到的最小值，也是递减的）。因此，`ans` 不会被更新，它会保持初值0。根据算法逻辑，如果 `ans` 保持为0，算法将返回-1，表示不存在任何两个元素满足 `num[j] > num[i]` 的条件。这是符合题目要求的正确行为。

在这个算法中，不需要区分这两种情况。无论是因为数组中所有元素相等，还是因为数组是单调递减的，都没有两个不同的索引 `i` 和 `j` 使得 `num[j] > num[i]`。在这两种情况下，`ans` 都会保持初始化的值0，最终算法返回-1。因此，这种设计恰当地处理了数组中元素完全相同或单调递减的情况，返回-1表示没有找到有效的索引对。

这个更新步骤是合理的。在每次迭代中，通过将 `cnt` 更新为 `cnt` 和当前元素 `num` 的最小值，确保 `cnt` 总是记录到当前位置为止的最小元素。这样，对于任何后续的元素，计算其与 `cnt` 的差值总是基于到目前为止最小的值进行的，这是计算最大差值所需的条件。因此，不会影响后续差值的计算，反而是确保了差值计算的正确性。