题目

给你一个下标从 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。注意：虽然 nums[0] - nums[1] 在数值上更大，但要求先下标小后下标大，不能把 j 放在 i 左边。

示例 2

项目	内容
输入	nums = [9,4,3,2]
输出	-1
解释	不存在同时满足「左下标小于右下标」且「左边元素小于右边元素」的数对。

示例 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

思路

从左向右扫描数组，维护「当前位置左侧」一段前缀里出现过的最小值，记为 minSoFar。对每一个下标 j（从 1 开始），先只看左侧，不与当前元素混淆：

• 若 minSoFar 严格小于 nums[j]，则说明在 j 左侧存在某个下标 i，满足 nums[i] 等于这段前缀的最小值且仍小于 nums[j]，此时用 nums[j] - minSoFar 更新答案更优，因为要让差值尽量大，左侧应取能参与比较的最小合法元素。
• 若 minSoFar 大于或等于 nums[j]，则说明左侧没有比 nums[j] 更小的数，这一轮不产生合法数对。

处理完位置 j 后，将 minSoFar 更新为「包含 nums[j] 在内的前缀最小值」，再继续向右。这样每个位置只常数次运算，整体为线性时间。

说明：条件「先出现的下标小于后出现的下标」由从左到右扫描自然保证；上面用行内代码形式写出比较关系，避免与页面里尖括号类标记冲突。

解法

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

总结

• 从左向右扫描数组，维护「当前位置左侧」一段前缀里出现过的最小值，记为 minSoFar。
• 对每一个下标 j（从 1 开始），先只看左侧，不与当前元素混淆：
• • 若 minSoFar 严格小于 nums[j]，则说明在 j 左侧存在某个下标 i，满足 nums[i] 等于这段前缀的最小值且仍小于 nums[j]，此时用 nums[j] - minSoFar 更新答案更优，因为要让差值尽量大，左侧应取能参与比较的最小合法元素。
• • 若 minSoFar 大于或等于 nums[j]，则说明左侧没有比 nums[j] 更小的数，这一轮不产生合法数对。
• 处理完位置 j 后，将 minSoFar 更新为「包含 nums[j] 在内的前缀最小值」，再继续向右。