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

题目描述

这是 LeetCode 上的 2016. 增量元素之间的最大差值 ，难度为 简单。

给你一个下标从 $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^9$

---

模拟

一个显然的做法是两层循环找合适的 i 和 j，这样的做法是 $O(n^2)$ 的。

利用我们目的是找到能够取得最大差值的数对，对于每个数对中的 $nums[i]$ 而言，对应的 $nums[j]$ 必然第是坐标 $i$ 左侧的最小值，因此可以通过边遍历边维护最小值 $min$ 的做法，从而将复杂度降到 $O(n)$。

代码：

class Solution {
    public int maximumDifference(int[] nums) {
        int n = nums.length, ans = -1;
        for (int i = 0, min = nums[0]; i < n; i++) {
            if (nums[i] > min) ans = Math.max(ans, nums[i] - min);
            min = Math.min(min, nums[i]);
        }
        return ans;
    }
}

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

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.2016 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。