leetcode_best_time_to_buy_and_sell_stock

发表于

难度：Easy

解题思路：最开始用了两次for循环，报错TLE。后来想，遍历数组，走到某一元素时，假设之前有了最大值max和最小值min。如果此元素比min小，那么继续往后遍历，可能会出现最大收益，这时我们更新max和min；如果此元素比max大，那么此时出现了比之前最大收益更大的值，更新max和最大收益变量。一开始不要想边界问题，先处理主要矛盾。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0) return 0;
        int max_profit = 0;
        int min_price = prices.front(), max_price = prices.front();
        for(auto it = prices.begin(); it != prices.end(); it++)
        {
            if(*it > max_price)
            {
                max_price = *it;
                max_profit = max(max_price-min_price, max_profit);
            }
            if(*it < min_price)
            {
                min_price = *it;
                max_price = *it;
            }
        }
        return max_profit;
    }
};

运行结果：6ms，超过48.52％

此题是一个O(n)的动态规划问题，维护一个min_price、max_profit。

每次迭代：
        max_profit = max(max_profit, prices[i]-min_price)

        min_price = min(min_price,prices[i])

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0)
            return 0;
        int min_price = prices[0];
        int max_profit = 0;
        for(int i = 1; i < prices.size(); i++)
        {
            max_profit = max(max_profit,prices[i]-min_price);
            min_price = min(min_price,prices[i]);
        }
        return max_profit;
    }
};

运行结果：9ms，超过15.20%

在此基础上还可以优化。维护一个min_price、max_price、max_profit。

每次迭代：
        prices[i] > max_price时，更新max_price，查看是否产生更大收益。

        prices[i] < min_price时，更新min_price和max_price。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0) return 0;
        int max_profit = 0;
        int min_price = prices.front(), max_price = prices.front();
        for(auto it = prices.begin(); it != prices.end(); it++)
        {
            if(*it > max_price)
            {
                max_price = *it;
                max_profit = max(max_price-min_price, max_profit);
            }
            if(*it < min_price)
            {
                min_price = *it;
                max_price = *it;
            }
        }
        return max_profit;
    }
};

运行结果：6ms，超过48.52％