增量元素之间的最大差值-LeetCode

2016. 增量元素之间的最大差值

🎯 问题描述（来源于LeetCode）

描述：
给你一个下标从 0 开始的整数数组 nums，该数组的大小为 n，请你找出 nums 中符合条件的最大差值 nums[j] - nums[i]。
条件：

1. 0 <= i < j < n
2. nums[i] < nums[j]

如果不存在符合条件的 i 和 j，返回 -1。

说明：

• 这是一个贪心算法问题，与“买卖股票的最佳时机”非常相似。

• 核心逻辑是维护一个“历史最小值”，并在遍历过程中计算当前值与历史最小值的差值。

• 通过一次遍历即可完成查找。

• 示例：

• 示例 1：

输入：nums = [7,1,5,4]
输出：4
解释：
- 选择 i = 1, j = 2。
- nums[1] = 1, nums[2] = 5。
- 差值 = 5 - 1 = 4。
- 这是满足条件的最大差值。

• 示例 2：

输入：nums = [9,4,3,2]
输出：-1
解释：
- 不存在满足条件的 i 和 j，因为数组是递减的。

💻 解题思路

思路1：贪心算法（一次遍历）

思路1：代码实现

class Solution:
    def maximumDifference(self, nums: List[int]) -> int:
        d = -1
        # 初始化最小值为一个较大的值（根据题目约束）
        min_num = 10**9
        
        for num in nums:
            # 更新历史最小值
            min_num = min(min_num, num)
            
            # 如果当前值大于历史最小值，计算差值并更新最大差值
            if num > min_num:
                d = max(d, num - min_num)
                
        return d

思路1：📊 性能分析

• 时间复杂度：$O(N)$
  • 其中 $N$ 是数组 nums 的长度。
  • 我们只遍历数组一次，每次操作都是常数时间。
  • 总时间复杂度为 $O(N)$。
• 空间复杂度：$O(1)$
  • 只使用了常数个额外变量（d 和 min_num）。

思考

1. 贪心策略：

   • 我们想要获得最大差值 nums[j] - nums[i]，就需要在 i 位置取最小值，在 j 位置取最大值。
   • 但是，必须满足 i < j 且 nums[i] < nums[j]。
   • 因此，我们维护一个“历史最小值” min_num，表示到目前为止（0 到 当前索引）的最小值。
   • 对于每个位置 j，我们计算 nums[j] - min_num，如果这个差值大于 0，就更新最大差值 d。

2. 变量初始化：

   • d = -1：初始化最大差值为 -1，表示如果不存在满足条件的差值，返回 -1。
   • min_num = 10**9：初始化最小值为一个较大的值。根据题目约束，nums[i] 最大为 $10^9$，所以这个初始值能保证第一次比较时 min_num 会被更新为第一个元素。
   • 优化：也可以将 min_num 初始化为 float('inf')，这样更加通用。

3. 逻辑流程：

   • 遍历数组中的每个元素 num。
   • 首先更新 min_num，确保它始终是到目前为止的最小值。
   • 然后检查当前值 num 是否大于 min_num。如果是，说明可以形成一个满足条件的差值 num - min_num，我们计算这个差值并更新 d。
   • 如果 num <= min_num，说明当前值比历史最小值还小（或相等），我们不会用这个值作为 j，但会更新 min_num。

4. 边界情况：

   • 数组长度为 1：min_num 被更新为唯一的值，num > min_num 不成立，返回 -1。
   • 数组单调递减：min_num 不断更新，num > min_num 始终不成立，返回 -1。
   • 数组单调递增：min_num 保持为第一个值，d 不断更新为最大差值。