題目

給你一個下標從 0 開始的整數(shù)數(shù)組 nums ，該數(shù)組的大小為 n ，請你計算 nums[j] - nums[i] 能求得的 最大差值 ，其中 0 <= i < j < n 且 nums[i] < nums[j] 。
返回 最大差值 。如果不存在滿足要求的 i 和 j ，返回 -1 。
示例 1：
輸入：nums = [7,1,5,4]
輸出：4
解釋：
最大差值出現(xiàn)在 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
解釋：
最大差值出現(xiàn)在 i = 0 且 j = 3 時，nums[j] - nums[i] = 10 - 1 = 9 。
提示：
n == nums.length
2 <= n <= 1000
1 <= nums[i] <= 10^9
來源：力扣（LeetCode）

解題思路

??最簡單的辦法就是兩層循環(huán)，遍歷查找最大的差值。

class Solution:def maximumDifference(self, nums: List[int]) -> int:MAX=-1for i in range(len(nums)):for j in range(i,len(nums)):if nums[j]>nums[i]:if nums[j]-nums[i]>MAX:MAX=nums[j]-nums[i]return MAX

??當然這是十分浪費時間的做法，時間復(fù)雜度達到了O(n^2)，另外一個做法是，可以在遍歷的過程中維持一個最小值，這個最小值是當前元素前面幾個元素的最小值，然后計算當前元素和最小值的差值，這樣時間復(fù)雜度就將為了O(n)

class Solution:def maximumDifference(self, nums: List[int]) -> int:MAX=-1MIN=nums[0]for i in range(1,len(nums)):if nums[i]>MIN:MAX=max(MAX,nums[i]-MIN)else:MIN=nums[i]return MAX

總結(jié)

以上是生活随笔為你收集整理的LeetCode简单题之增量元素之间的最大差值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。