leetcode 2016. Maximum Difference Between Increasing Elements（python）

「 This is my participation 11 The fourth of the yuegengwen challenge 12 God , Check out the activity details ：2021 One last more challenge 」

describe

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.
 Copy code 

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].
 Copy code 

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.
 Copy code 

Note:

• n == nums.length
• 2 <= n <= 1000
• 1 <= nums[i] <= 10^9

analysis

According to the meaning , Give an example from 0 The start index length is n A list of nums , find nums[j] - nums[i] Maximum difference between , And 0 <= i < j < n , And nums[i] < nums[j] . If there is a maximum difference, return , Otherwise return to -1 .

The simplest way is the double cycle of violence ：

• Initialization result result by -1
• Traverse range(len(nums)-1) Every element in i , Re traversal range(i+1, len(nums)) Every element in j , If nums[j] <= nums[i] Then continue to the next cycle , Otherwise, use result Record nums[j]-nums[i] The maximum of
• Return after traversal result

answer

class Solution(object):
    def maximumDifference(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = -1 
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                if nums[j] <= nums[i]:
                    continue
                result = max( result , nums[j]- nums[i])
        return result

        	      
		
 Copy code 

Running results

Runtime: 316 ms, faster than 16.50% of Python online submissions for Maximum Difference Between Increasing Elements.
Memory Usage: 13.6 MB, less than 20.57% of Python online submissions for Maximum Difference Between Increasing Elements.
 Copy code 

analysis

You can also traverse once to find the maximum difference ,, Ideas ：

• Initialization result result by -1 ,minNum by nums[0] Indicates the current minimum value
• Start with the second element , Each element traversed from left to right , If nums[i] Greater than the current minimum minNum , Is executed max(result, nums[i]-minNum) to update result , And then execute min(minNum, nums[i]) Update the current minimum minNum
• Return after traversal result that will do

answer

class Solution(object):
    def maximumDifference(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = -1 
        minNum = nums[0]
        for i in range(1, len(nums)):
            if nums[i]>minNum:
                result = max(result, nums[i]-minNum)
            minNum = min(minNum, nums[i])
        return result
 Copy code 

Running results

Runtime: 36 ms, faster than 60.29% of Python online submissions for Maximum Difference Between Increasing Elements.
Memory Usage: 13.6 MB, less than 20.57% of Python online submissions for Maximum Difference Between Increasing Elements.
 Copy code 

Original link ：leetcode.com/problems/ma…

Your support is my greatest motivation