[leetcode daily question] - 121. The best time to buy and sell stocks

One 【 Topic category 】

• Array

Two 【 questions 】

• Simple

3、 ... and 【 Title number 】

• 121. The best time to buy and sell stocks

Four 【 Title Description 】

• 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 .

5、 ... and 【 Title Example 】

• 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.

6、 ... and 【 Topic tips 】

• $1<=prices.length<=10^5$
• $0<=prices[i]<=10^4$

7、 ... and 【 Their thinking 】

• This problem can easily think of two levels $for$ loop , But some of these examples will time out （ The time complexity is ：$O(N^2)$, among $N$ Is array length ）, The reason is that there are many unnecessary judgments , So we need to think about how to reduce these redundant judgments , You can find the maximum profit faster
• So we can easily think of greedy algorithm , We should maximize profits , That is to say, the minimum price to buy , The highest selling price , But we should pay attention to buying first , It's selling , This can be seen more clearly through examples
• Based on this idea , We maintain maxProfit Initialize to 0, That is, the minimum profit is 0,minPrice Initialize to the first value of the array , When searching backwards , If you encounter more than minPrice A small value is assigned to minPrice It means you can buy at a lower price , As for which day to sell, just search backwards , Subtraction is profit , If the profit is greater than what we maintain maxProfit, Just update maxProfit
• Return at the end of the loop maxProfit that will do

8、 ... and 【 Time frequency 】

• Time complexity ：$O(N)$, among $N$ Is array length
• Spatial complexity ：$1$

Nine 【 Code implementation 】

1. Java Language version

package Array;

public class p121_TheBestTimeToBuyAndSellStocks {
    

    public static void main(String[] args) {
    
        int[] prices = {
    7, 1, 5, 3, 6, 4};
        int res = maxProfit(prices);
        System.out.println(res);
    }

    public static int maxProfit(int[] prices) {
    
        int maxProfit = 0;
        int minPrice = prices[0];
        for (int i = 0; i < prices.length; i++) {
    
            if (prices[i] < minPrice) {
    
                minPrice = prices[i];
            }
            if ((prices[i] - minPrice) > maxProfit) {
    
                maxProfit = prices[i] - minPrice;
            }
        }
        return maxProfit;
    }

}

2. C Language version

#include<stdio.h>

int maxProfit(int* prices, int pricesSize)
{
    
	int maxProfit = 0;
	int minPrice = prices[0];
	for (int i = 0; i < pricesSize; i++)
	{
    
		if (prices[i] < minPrice)
		{
    
			minPrice = prices[i];
		}
		if ((prices[i] - minPrice) > maxProfit)
		{
    
			maxProfit = prices[i] - minPrice;
		}
	}
	return maxProfit;
}

/* The main function is omitted */

Ten 【 Submit results 】

1. Java Language version
   

2. C Language version