Leetcode 2016. Maximum Difference Between Increasing Elements

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

Maximum Difference Between Increasing Elements

2. Solution

解析:Version 1,两层循环遍历,O(N^2)。

  • Version 1
1
2
3
4
5
6
7
8
9
class Solution:
def maximumDifference(self, nums: List[int]) -> int:
length = len(nums)
diff = -1
for i in range(length):
for j in range(i+1, length):
if nums[j] > nums[i]:
diff = max(diff, nums[j] - nums[i])
return diff

解析:Version 2,从左向右遍历,minimum始终保持左半部分最小值,如果当前数字numminimum大,求二者的difference,取difference最大值,O(N)。

  • Version 2
1
2
3
4
5
6
7
8
9
10
class Solution:
def maximumDifference(self, nums: List[int]) -> int:
length = len(nums)
diff = -1
minimum = nums[0]
for num in nums:
if num > minimum:
diff = max(diff, num - minimum)
minimum = min(minimum, num)
return diff

Reference

  1. https://leetcode.com/problems/maximum-difference-between-increasing-elements/
如果有收获,可以请我喝杯咖啡!