1 题目

122-买卖股票的最佳时机II

2 思路

遍历数组，价格低就买，价格高就卖。股民的理想玩法，低买高卖，赚得盆满钵满。

时间复杂度：O(n)，空间复杂度：O(1)。

3 题解

class Solution {
 public:
  int maxProfit(vector<int>& prices) {
    int n = prices.size();
    int profit = 0, buy, sell;
    int i = 0;

    while (i < n - 1) {
      while (i < n - 1 && prices[i] >= prices[i + 1]) ++i;
      if (i < n - 1) {
        buy = prices[i++];
      } else {
        break;
      }

      while (i < n - 1 && prices[i] <= prices[i + 1]) ++i;
      if (i < n) {
        sell = prices[i++];
      } else {
        break;
      }

      profit += sell - buy;
    }

    return profit;
  }
};

太不优雅了。还是看看官方题解吧。

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

    return ans;
  }
};

不需要费力去找局部最小值和局部最大值，而是每一步都计算收益，累加收益为正的值就好了。