121. The best time to buy or sell stocks

create by db on 2021-3-8 23:28:00

Recently revised in 2021-3-8 23:48:57

Idle time to have a tight mind, busy time to have leisure fun

121. The best time to buy and sell stocks

directory

  • Topic describes
  • Thought analysis
  • AC code
  • conclusion

Topic describes

Returns the directory

Given an array prices, its ith element prices[I] represents the price of a given stock on day I.

You can only buy the stock on one day and sell it on a different day in the future. Design an algorithm to calculate the maximum profit you can make.

Return the maximum profit you can make from the transaction. If you can’t make any profit, return 0.

Example 1:

Input: [7,1,5,3,6,4] output: 5 explanation: buy on day 2 (stock price = 1) and sell on day 5 (stock price = 6), maximum profit = 6-1 = 5. Note that the profit cannot be 7-1 = 6, because the selling price needs to be higher than the buying price; Also, you can't sell stocks before you buy them.Copy the code

Example 2:

Input: prices = [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the code

Tip:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104

Thought analysis

 

Idea 1: Violent traversal

The maximum difference between the two numbers in the array is the maximum profit maxprofit

Max (prices[j] – prices[I]) (j > I)

  • Time complexity: O(n^2), run n(n-1)/2 times
  • Space complexity: O(1), using only constant variables

tips:

Unfortunately, this algorithm has been ruled timeout by LeetCode…

Idea 2: Iterate once

📈 Buy low and sell high to make money

  • A variable minPrice is storedAll-time low
  • A variable Max is storedThe biggest profits

If you walk through the array, there are two possibilities

  1. If the current value is less than the historical low, the historical low is updated

  2. If the current value is greater than the historical low, the maximum profit is updated by taking the larger value between [current value – historical low] and the maximum profit

Just loop it once

  • Time complexity :O(n)
  • Space complexity :O(1)

AC code

Solution 1: Violent traversal

/ * * *@param {number[]} prices
 * @return {number}* /
var maxProfit = function(prices) {
    let max = 0;
    for (let i = 0; i < prices.length; i++) {
        for(let j = i + 1; j < prices.length; j++) {
            if(prices[j] > prices[i]) {
                max = Math.max(prices[j] - prices[i], max); }}}return max;
};
Copy the code

Solution 2: A traversal

/ * * *@param {number[]} prices
 * @return {number}* /
var maxProfit = function(prices) {
    let minprice = prices[0]
    let max = 0
    for(let i = 0; i<prices.length; i++){if(prices[i]<minprice){
            minprice = prices[i]
        }else{
            max = Math.max(max,prices[i]-minprice)
        }
    }
    return max
};;
Copy the code

conclusion

Returns the directory

March hello, spring flowers. I want to enter dachang! Come on!

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign

Postscript: Hello friends, if you think this article is good, remember to give a thumbs-up or star, your thumbs-up and star is my motivation to write more and richer articles!Making the address

Document agreement



dbThe document library 由 dbusingCreative Commons Attribution – Non-commercial Use – Same way Share 4.0 International LicenseGrant permission.

Based on thegithub.com/danygitgitOn the creation of works.

Use rights other than those authorized by this License agreement may be obtained fromCreativecommons.org/licenses/by…Obtained.