Leetcode 每日一题5 Best Time to Buy and Sell Stock II

题意

给一个数组，表示每天的股票股价。可以进行无数次交易，但同一时刻只能持有一股的股票。求最大收益。

思路

假如股价在未来是涨的，那么就应该购买。假如是跌的，就不购买。

因此，我们扫描一遍数组，维护当前最低的股价，假如遇到较高的股价，就卖出，并更新最低股价。时间复杂度为O(n)，空间复杂度为O(1)。

代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) {
            return 0;
        }
        int mi = prices[0];
        int ans = 0;
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] - mi > 0) {
                ans += prices[i] - mi;
                mi = prices[i];
            }
            mi = min(mi, prices[i]);
        }
        return ans;
    }
};