剑指offer-75、买卖股票的最好时机

题⽬描述

假设你有⼀个数组 prices ，⻓度为 n ，其中 prices 是股票在第 i 天的价格，请根据这个价格数组，返回买卖股票能获得的最⼤收益

• 你可以买⼊⼀次股票和卖出⼀次股票，并⾮每天都可以买⼊或卖出⼀次，总共只能买⼊和卖出⼀次，且买⼊必须在卖出的前⾯的某⼀天
  
• 如果不能获取到任何利润，请返回 0
  
• 假设买⼊卖出均⽆⼿续费
  

示例1：
输⼊：[8,9,2,5,4,7,1]
返回值: 5
说明: 在第3天(股票价格 = 2)的时候买⼊，在第6天(股票价格 = 7)的时候卖出，最⼤利润 = 7-2 = 5，不能选择在第2天买⼊，第3天卖出，这样就亏损7了；同时，你也不能在买⼊前卖出股票。
示例2：
输⼊：[2,4,1]
返回值: 2
思路及解答

暴⼒穷举

这⾥涉及的节点⽆⾮是买⼊，卖出，那么我们遍历所有的数据，作为买⼊⽇期，同时将该⽇期后⾯每⼀个都作为卖出⽇期来计算，只要维护最⼤的利润即可。

1. public class Solution {
2.     public int maxProfit(int[] prices) {
3.         if (prices == null || prices.length < 2) {
4.             return 0;
5.         }
6.         
7.         int maxProfit = 0;
8.         int n = prices.length;
9.         
10.         // 外层循环：遍历所有可能的买入点
11.         for (int i = 0; i < n - 1; i++) {
12.             // 内层循环：遍历所有可能的卖出点（必须在买入点之后）
13.             for (int j = i + 1; j < n; j++) {
14.                 int profit = prices[j] - prices[i];
15.                 if (profit > maxProfit) {
16.                     maxProfit = profit;
17.                 }
18.             }
19.         }
20.         
21.         return maxProfit;
22.     }
23. }

复制代码

• 时间复杂度： O(n2)
  
• 空间复杂度：O(1)
  

贪⼼法（最优解）

我们要想得到⼀个最⼤的利润，其实就是要两者差值最⼤。如果让差值最⼤，假设在当天卖出，那么什么时候买⼊最好呢？
当然是在前⾯找到最⼩的买⼊点，⽐如：

⽽前⾯的最⼩值，其实我们在遍历的时候是可以不断维护的，所以我们只要遍历⼀次数组即可。
关键思想：

• 最大利润 = 某日价格 - 该日之前的最低价格
  
• 只需维护两个变量：
  
  
  
  • minPrice：遍历过程中遇到的最低价格
    
  • maxProfit：当前能获得的最大利润
    
  
  

1. public class Solution63 {
2.     public int maxProfit(int[] prices) {
3.         int min = Integer.MAX_VALUE;
4.         int result = 0;
5.         for (int value: prices) {
6.             // 维护最⼩值
7.             min = Math.min(min, value);
8.             // 当前值减去前⾯最⼩值，与利润最⼤值对⽐，维护好利润最⼤值
9.             result = Math.max(result, value - min);
10.         }
11.         return result;
12.     }
13. }

复制代码

• 时间复杂度：O(n)，只需遍历一次数组
  
• 空间复杂度：O(1)，只使用常数空间
  

执行过程示例（prices = [8,9,2,5,4,7,1]）

1. i=0: price=8, minPrice=8, maxProfit=0
2. i=1: price=9, minPrice=8, maxProfit=1
3. i=2: price=2, minPrice=2, maxProfit=1
4. i=3: price=5, minPrice=2, maxProfit=3
5. i=4: price=4, minPrice=2, maxProfit=3
6. i=5: price=7, minPrice=2, maxProfit=5
7. i=6: price=1, minPrice=1, maxProfit=5
8. 结果：5

复制代码

动态规划

dp表示前i天的最大利润，状态转移基于前i-1天的结果
状态定义：

• minPrice：前i天的最低价格
  
• maxProfit：前i天能获得的最大利润
  

1. public class Solution {
2.     public int maxProfit(int[] prices) {
3.         if (prices == null || prices.length < 2) {
4.             return 0;
5.         }
6.         
7.         int minPrice = prices[0];
8.         int maxProfit = 0;
9.         
10.         for (int i = 1; i < prices.length; i++) {
11.             // 状态转移方程：
12.             // 前i天的最大利润 = max(前i-1天的最大利润, 第i天价格-前i-1天的最低价格)
13.             maxProfit = Math.max(maxProfit, prices[i] - minPrice);
14.             minPrice = Math.min(minPrice, prices[i]);
15.         }
16.         
17.         return maxProfit;
18.     }
19. }

复制代码

• 时间复杂度：O(n)，单次遍历
  
• 空间复杂度：O(1)，优化后只需两个变量
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

感谢发布原创作品，程序园因你更精彩

过来提前占个楼