Leetcode 2016. Maximum Difference Between Increasing Elements

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

1. Description

2. Solution

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

• Version 1

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始终保持左半部分最小值，如果当前数字num比minimum大，求二者的difference，取difference最大值，O(N)。

• Version 2

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/