LeetCode 122. Best Time to Buy and Sell Stock II[Easy].md

发表于 更新于 阅读次数：

题目

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

1
2
3
4
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

1
2
3
4
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

1
2
3
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e., max profit = 0.

Constraints:

  • 1 <= prices.length <= 3 * 104
  • 0 <= prices[i] <= 104

题解

解答1[Java]

1
2
3
4
5
6
7
8
9
10
11
public class Problem122Solution1 {
    public int maxProfit(int[] prices) {
        int totalProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            totalProfit += Math.max(0, prices[i] - prices[i - 1]);
        }

        return totalProfit;
    }
}

思路

假设股价是连续上涨的，比如 [1, 2, 3, 4, 5]，那么我们第一天买，然后第 5 天卖，其实等价于，第 1 天买，第 2 天卖，第 2 天再买， 第 3 天再卖。只要后一天比前一天价格高，我们就做操作。反之，如果后一天比前一天估计低，我们就不操作。

这种思路其实就是贪心算法的思路。

参考资料

  1. 股票问题系列通解（转载翻译） - 力扣（LeetCode）
  2. 一个方法团灭 LeetCode 股票买卖问题 | labuladong 的算法笔记