本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

Given a 0-indexed integer array nums of size n, find the maximum difference between nums[i] and nums[j] (i.e., nums[j] - nums[i]), such that 0 <= i < j < n and nums[i] < nums[j].

Return the maximum difference. If no such i and j exists, return -1.

Example 1:

Input: nums = [7,1,5,4]
Output: 4
Explanation:
The maximum difference occurs with i = 1 and j = 2, nums[j] - nums[i] = 5 - 1 = 4.
Note that with i = 1 and j = 0, the difference nums[j] - nums[i] = 7 - 1 = 6, but i > j, so it is not valid.

Example 2:

Input: nums = [9,4,3,2]
Output: -1
Explanation:
There is no i and j such that i < j and nums[i] < nums[j].

Example 3:

Input: nums = [1,5,2,10]
Output: 9
Explanation:
The maximum difference occurs with i = 0 and j = 3, nums[j] - nums[i] = 10 - 1 = 9.

Constraints:

• n == nums.length
• 2 <= n <= 1000
• 1 <= nums[i] <= 109

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

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

---

解法1 暴力

直接暴力双重循环。对每个 nums[i] ，都与其后的每个 nums[j] 比较并计算差值。算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2) ，空间复杂度为 O ( 1 ) O(1) O(1) ：

//C++ version
class Solution {
public:
    int maximumDifference(vector<int>& nums) {
        int ans = -1;
        for (int i = 0, n = nums.size(); i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                if (nums[i] < nums[j])
                    ans = max(ans, nums[j] - nums[i]);
        return ans;
    }
};
//执行用时：24 ms, 在所有 C++ 提交中击败了40.26% 的用户
//内存消耗：8.2 MB, 在所有 C++ 提交中击败了7.19% 的用户

---

解法2 前缀最小值

在遍历数组时不断更新前缀最小值，如果前缀最小值小于 nums[i] ，我们就得到了答案的一个候选。算法时间复杂度为 O ( n ) O(n) O(n) ，空间复杂度为 O ( 1 ) O(1) O(1) ：

//C++ version
class Solution {
public:
    int maximumDifference(vector<int>& nums) {
        int ans = -1, premin = nums[0];
        for (int i = 1, n = nums.size(); i < n; ++i) {
            if (premin < nums[i]) ans = max(ans, nums[i] - premin);
            else premin = nums[i];
        }
        return ans;
    }
};
//执行用时：4 ms, 在所有 C++ 提交中击败了93.17% 的用户
//内存消耗：8.1 MB, 在所有 C++ 提交中击败了36.52% 的用户