LeetCode_动态规划_简单_121.买卖股票的最佳时机

Love The Way You Lie 2023-10-06 19:18 27阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个数组 prices ，它的第 i 个元素 prices\[i\] 表示一支给定股票第 i 天的价格。  
**你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票**。设计一个算法来计算你所能获取的最大利润。  
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。

**示例 1：**  
输入：\[7,1,5,3,6,4\]  
输出：5  
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6 -1 = 5 。注意利润不能是 7 - 1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

**示例 2：**  
输入：prices = \[7,6,4,3,1\]  
输出：0  
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

**提示：**  
1 <= prices.length <= 105  
0 <= prices\[i\] <= 104

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock

## 2.思路 ##

（1）暴力穷举法  
使用两层 for 循环穷举出所有的可能性，然后取最大的利润即可，但是此方法时间复杂度较高，在 LeetCode 中提交时会出现超时现象。

（2）一次遍历  
① 用变量 minprice 来记录买入的历史最低价格，其初始值为 Integer.MAX\_VALUE；  
② 用变量 maxprofit 来记录最大利润，初始值为 0；  
③ 开始遍历数组 prices：  
1）如果该天买入的价格 prices\[i\] < minprice，则更新 minprice；  
1）如果该天买入股票并且能够获取的利润大于 maxprofit，则更新 maxprofit；  
④ 当遍历结束后，maxprofit 即为最大利润，将其返回即可。

（3）动态规划  
LeetCode股票问题的算法框架可参考[团灭 LeetCode 股票买卖问题][LeetCode]。

相关题目：  
[LeetCode\_动态规划\_中等\_122.买卖股票的最佳时机 II][LeetCode_122._ II]  
[LeetCode\_动态规划\_困难\_123.买卖股票的最佳时机 III][LeetCode_123._ III]  
[LeetCode\_动态规划\_困难\_188.买卖股票的最佳时机 IV][LeetCode_188._ IV]  
[LeetCode\_动态规划\_中等\_309.最佳买卖股票时机含冷冻期][LeetCode_309.]  
[LeetCode\_动态规划\_中等\_714.买卖股票的最佳时机含手续费][LeetCode_714.]

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public int maxProfit(int[] prices) {
        
            int length = prices.length;
            int maxProfit = 0; 
            for (int i = 0; i < length - 1; i++) {
        
                for (int j = i + 1; j < length; j++) {
        
                    if (prices[i] < prices[j]) {
        
                        maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
                    }
                }
            }
            return maxProfit;
        }
    }

//思路2————一次遍历
    class Solution {
        
        public int maxProfit(int[] prices) {
        
            //用 minPrice 记录买入的历史最低价格
            int minPrice = Integer.MAX_VALUE;
            //最大利润，初始值为 0
            int maxProfit = 0;
            for (int price : prices) {
        
                if (price < minPrice) {
        
                    minPrice = price;
                } else if (price - minPrice > maxProfit) {
        
                    //如果该天买入股票并且能够获取的利润大于 maxProfit，则更新 maxProfit
                    maxProfit = price - minPrice;
                }
            }
            return maxProfit;
        }
    }

//思路3————动态规划
    class Solution {
        
    	public int maxProfit(int[] prices) {
        
    	    int length = prices.length;
    	    /*
    	    	定义 dp 数组 dp[i][2](0 ≤ i ≤ length)，其中
    	        dp[i][0]:第 i 天结束后手中没有股票的最大利润
    	        dp[i][1]:第 i 天结束后手中持有股票的最大利润
    	        该问题共有 i * 2 种状态
    	    */
    	    int[][] dp = new int[length][2];
    	    dp[0][0] = 0;
    	    dp[0][1] = -prices[0];
    	    for (int i = 1; i < length; i++) {
        
    	    	/*
    	    		第 i 天手中没有股票的两种状态选择:
    	    		(1) dp[i - 1][0]: 与前一天一样，手中没有股票
    	    		(2) dp[i - 1][1] + prices[i]: 卖掉前一天手中持有的股票
    			*/
    	        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
    	        /*
    	        	第 i 天手中持有股票的两种状态选择:
    	    		(1) dp[i - 1][1]: 保留前一天手中持有的股票
    	    		(2) -prices[i]: 买入当天的股票
    			*/
    	        dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
    	    }
    	    // dp[length - 1][0]: 最后一天手中没有股票所得到的最大利润
    	    return dp[length - 1][0];
    	}
    }
    
    //使用滚动数组降低上面代码的空间复杂度
    class Solution {
        
    	public int maxProfit(int[] prices) {
        
    	    int n = prices.length;
    	    // base case: dp[-1][0] = 0, dp[-1][1] = -prices[0]
    	    int dp_i_0 = 0;
    	    int dp_i_1 = -prices[0];
    	    for (int i = 0; i < n; i++) {
        
    	        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
    	        dp_i_1 = Math.max(dp_i_1, -prices[i]);
    	    }
    	    return dp_i_0;
    	}
    }

[LeetCode]: https://mp.weixin.qq.com/s/4nqJMIyCKQD7IJ-HI6S3Vg
[LeetCode_122._ II]: https://blog.csdn.net/weixin_43004044/article/details/120210000
[LeetCode_123._ III]: https://blog.csdn.net/weixin_43004044/article/details/120228372
[LeetCode_188._ IV]: https://blog.csdn.net/weixin_43004044/article/details/123269023
[LeetCode_309.]: https://blog.csdn.net/weixin_43004044/article/details/123284002
[LeetCode_714.]: https://blog.csdn.net/weixin_43004044/article/details/123290744