【一天一道LeetCode】#121. Best Time to Buy and Sell Stock

时间:2021-09-07 19:45:52

#

一天一道LeetCode

本系列文章已全部上传至我的github,地址:ZeeCoder‘s Github

欢迎大家关注我的新浪微博,我的新浪微博

欢迎转载,转载请注明出处

(一)题目

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]

Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]

Output: 0

In this case, no transaction is done, i.e. max profit = 0.

(二)解题

题目大意:给定一个数组表示一天之内的股价变化,只有一次买卖机会,如何做到利润最大。

解题思路:考虑采用两个指针i和j以及一个maxpro,第i时刻买,第j时刻卖(i

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int maxpro = 0;//表示最大利润
        int i = 0;//第i时刻买
        for(int j = 1 ; j < n ; j++)
        {
            if(prices[j]>prices[i]){//当大于买时的价钱时
                int temp = prices[j] - prices[i];//计算利润
                maxpro = max(maxpro,temp);//更改maxpro,保存最大利润值
            }
            else
            {
                i=j;//新的买时刻
            }
        }
        return maxpro;//返回最大利润
    }
};