current position:Home>leetcode 2016. Maximum Difference Between Increasing Elements(python)
leetcode 2016. Maximum Difference Between Increasing Elements(python)
2022-01-31 11:19:21 【Wang Daya】
「 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
copyright notice
author[Wang Daya],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201311119190008.html
The sidebar is recommended
- [algorithm learning] 1108 IP address invalidation (Java / C / C + + / Python / go / trust)
- Test platform series (71) Python timed task scheme
- Java AES / ECB / pkcs5padding encryption conversion Python 3
- Loguru: the ultimate Python log solution
- Blurring and anonymizing faces using OpenCV and python
- How fast Python sync and async execute
- Python interface automation test framework (basic) -- common data types list & set ()
- Python crawler actual combat, requests module, python realizes capturing video barrage comments of station B
- Python: several implementation methods of multi process
- Sword finger offer II 054 Sum of all values greater than or equal to nodes | 538 | 1038 (Java / C / C + + / Python / go / trust)
guess what you like
-
How IOS developers learn python programming 3-operator 2
-
How IOS developers learn python programming 2-operator 1
-
[Python applet] 8 lines of code to realize file de duplication
-
Python uses the pynvml tool to obtain the working status of GPU
-
Data mining: Python actual combat multi factor analysis
-
Manually compile opencv on MacOS and Linux and add it to Python / C + + / Java as a dependency
-
Use Python VTK to batch read 2D slices and display 3D models
-
Complete image cutting using Python version VTK
-
Python interface automation test framework (basic) -- common data types Dict
-
Django (make an epidemic data report)
Random recommended
- Python specific text extraction in actual combat challenges the first step of efficient office
- Daily python, Part 8 - if statement
- Django model class 1
- The same Python code draws many different cherry trees. Which one do you like?
- Python code reading (Chapter 54): Fibonacci sequence
- Django model class 2
- Python crawler Basics
- Mapping 3D model surface distances using Python VTK
- How to implement encrypted message signature and verification in Python -- HMAC
- leetcode 1945. Sum of Digits of String After Convert(python)
- leetcode 2062. Count Vowel Substrings of a String(python)
- Analysis of Matplotlib module of Python visualization
- Django permission management
- Python integrated programming -- visual hot search list and new epidemic situation map
- [Python data collection] scripy realizes picture download
- Python interface automation test framework (basic part) -- loop statement of process control for & while
- Daily python, Chapter 9, while loop
- Van * Python | save the crawled data with docx and PDF
- Five life saving Python tips
- Django frequency control
- Python - convert Matplotlib image to numpy Array or PIL Image
- Python and Java crawl personal blog information and export it to excel
- Using class decorators in Python
- Untested Python code is not far from crashing
- Python efficient derivation (8)
- Python requests Library
- leetcode 2047. Number of Valid Words in a Sentence(python)
- leetcode 2027. Minimum Moves to Convert String(python)
- How IOS developers learn Python Programming 5 - data types 2
- leetcode 1971. Find if Path Exists in Graph(python)
- leetcode 1984. Minimum Difference Between Highest and Lowest of K Scores(python)
- Python interface automation test framework (basic) -- basic syntax
- Detailed explanation of Python derivation
- Python reptile lesson 2-9 Chinese monster database. It is found that there is a classification of color (he) desire (Xie) monsters during operation
- A brief note on the method of creating Python virtual environment in Intranet Environment
- [worth collecting] for Python beginners, sort out the common errors of beginners + Python Mini applet! (code attached)
- [Python souvenir book] two people in one room have three meals and four seasons: 'how many years is it only XX years away from a hundred years of good marriage' ~?? Just come in and have a look.
- The unknown side of Python functions
- Python based interface automation test project, complete actual project, with source code sharing
- A python artifact handles automatic chart color matching