Leetcode 0121. the best time to buy and sell stocks - simulation from back to front

【LetMeFly】121. The best time to buy and sell stocks - Simulate from back to front

Force button topic link ：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/

Given an array prices , It's the first  i Elements  prices[i] Represents the number of shares in a given stock i Sky price .

You can only choose One day Buy this stock , And choose A different day in the future Sell the stock . Design an algorithm to calculate the maximum profit you can get .

Return the maximum profit you can make from the deal . If you can't make any profit , return 0 .

 

Example 1：

 Input ：[7,1,5,3,6,4]
 Output ：5
 explain ： In the  2  God （ Stock price  = 1） Buy when , In the  5  God （ Stock price  = 6） Sell when , Maximum profit  = 6-1 = 5 .
      Note that profit cannot be  7-1 = 6,  Because the selling price needs to be higher than the buying price ; meanwhile , You can't sell stocks before you buy them .

Example 2：

 Input ：prices = [7,6,4,3,1]
 Output ：0
 explain ： under these circumstances ,  No deal is done ,  So the biggest profit is  0.

 

Tips ：

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

Method 1 ： Simulate from back to front

Use two variables ：

int M = 0;  //  Represents the highest stock price today and one day after 
int ans = 0;  //  Represents maximum benefit 

Go back and forth , Keep updating the maximum $M$.

Because we traverse from back to front , So if you buy stocks today , It must be able to sell at a stock price of $M$ Sell when .

such , If you buy stocks today , How much money you can earn .

• Time complexity $O(N)$, among $N$ Is the number of days for which the stock amount is known .
• Spatial complexity $O(1)$

AC Code

C++

class Solution {
    
public:
    int maxProfit(vector<int>& prices) {
    
        int ans = 0;
        int M = 0;
        for (int i = prices.size() - 1; i >= 0; i--) {
    
            M = max(M, prices[i]);
            ans = max(ans, M - prices[i]);  //  If you buy stocks today , The biggest benefit is  M - prices[i]
        }
        return ans;
    }
};

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125867999