数据规模 n <= 1000。O(n2) 的算法也是能过的。
方法1: Brute Force
双重循环枚举所有的(nums[i], nums[j])的组合。
时间复杂度：O(n2)
空间复杂度：O(1)
|
1 2 3 4 5 6 7 8 9 10 11 |
class Solution { public: int maximumDifference(vector<int>& nums) { const int n = nums.size(); int ans = 0; for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) ans = max(ans, nums[j] - nums[i]); return ans ? ans : -1; } }; |
方法2: 空间换时间
使用prefix sum算法，预先计算num[i] ~ nums[n-1]的最大值，存储在right[i]中。
时间复杂度：O(n)
空间复杂度：O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: int maximumDifference(vector<int>& nums) { const int n = nums.size(); int ans = 0; vector<int> right(n, nums.back()); for (int i = n - 2; i >= 0; --i) right[i] = max(right[i + 1], nums[i]); for (int i = 0; i < n; ++i) ans = max(ans, right[i] - nums[i]); return ans ? ans : -1; } }; |
方法3: Running Min
从左到右遍历，记录当前为止出现过最小的值。比较 nums[i] – 最小值 和 最优解。
时间复杂度：O(n)
空间复杂度：O(1)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public: int maximumDifference(vector<int>& nums) { const int n = nums.size(); int ans = 0; int smallest = nums[0]; for (int i = 1; i < n; ++i) { ans = max(ans, nums[i] - smallest); smallest = min(smallest, nums[i]); } return ans ? ans : -1; } }; |