【LeetCode】Best Time to Buy and Sell Stock Ⅰ、Ⅱ、Ⅲ【Java】

灰太狼 2021-09-21 05:44 212阅读 0赞

# 121. Best Time to Buy and Sell Stock #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]  
题意为只可买入一次，并卖出一次，要求获取的利润最高。最简单的思路就是两层循环，比较每一个数与后面的数的差值，以求出当前能获取的最大差值，即为最大利润，算法的时间复杂度即O(n²)。我们可以考虑优化算法，我们每获取一个数时，我们其实`只需要跟这个数之前最小的那个数做比较`，就可以知道这个为出口时，能获取的最大利润值，再通过比较所有出口的最大利润值，来获取一个全局最优解。

public int maxProfit(int[] prices) { 
            if (prices == null || prices.length <= 1) { 
                return 0;
            }
    
            int minValue = Integer.MAX_VALUE;
            int maxProfit = 0;
            for (int price : prices) { 
                if (price < minValue) { 
                	// 更新当前的遍历过得数组的最小值
                    minValue = price;
                } else if (price - minValue > maxProfit) { 
                	// 计算当前位置为出口时的最大利润
                	// 如超过全局最优，则覆盖全局最优
                    maxProfit = price - minValue;
                }
            }
            return maxProfit;
        }

# 122. Best Time to Buy and Sell Stock II #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 1]  
第二题与第一题的区别在于，现在不需要考虑买卖的次数，可以无数次进行买入卖出。那解题思路变的很容易，我们只需要不断加上数组连续数之间的差值，即能得到一个总的利润（贪心的思想）。代码如下：

public int maxProfit(int[] prices) { 
            if (prices == null || prices.length == 0) { 
                return 0;
            }
    
            int maxProfit = 0;
            for (int i = 1; i < prices.length; i++) { 
                if (prices[i] - prices[i - 1] > 0) { 
                    maxProfit += prices[i] - prices[i - 1];
                }
            }
            return maxProfit;
        }

# 123. Best Time to Buy and Sell Stock III #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 2]  
对于第三题，其约束了买入卖出的次数，至多两次。我们可以考虑，将买入卖出2次，看成了四次行为，即`买1`、`卖1`、`买2`、`卖2`，因为只有手头上的钱才是钱，即购买股票可视为支出（或亏损），即购买 price 时，当日的收益为 buy = -price，而卖出视为收入，收益需要考虑支出，即卖出价位为 price 时，总收益为 buy + price。而，我们第二次的购买，会受到第一次买入结果的影响，因此，第二次购入时，其收益为 sell1 - price。代码如下：

public int maxProfit(int[] prices) { 
            int b1 = Integer.MIN_VALUE, s1 = 0;
            int b2 = Integer.MIN_VALUE, s2 = 0;
            for (int price : prices) { 
                // 第一次买入，支出 price
                b1 = Math.max(b1, -price);
                // 第一次卖出，盈利 price + b1
                s1 = Math.max(s1, price + b1);
    
                // 第二次买入，受第一次买卖的影响，因此有 s1 的本金，支出 price
                b2 = Math.max(b2, s1 - price);
                // 第二次买入，盈利 price + b2 
                s2 = Math.max(s2, price + b2);
            }
            return s2;
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]: /images/20210920/d10c6fc2b93f43b59eabce953fb4d5fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 1]: /images/20210920/28f096f1630847c385a0c4166d7f80c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 2]: /images/20210920/f3bdc8a5108a47fda98cd1a2bea4a2bb.png