leetcode-121. 买卖股票的最佳时机-多解+动态规划(DP)入门_leetcode买卖股票最佳时机

121. 买卖股票的最佳时机

思路

理解题意，这里的最佳时机是：你在某一天买入该股票，不断的尝试在某一天卖出的利润最大化（贪心？）；又因为存在状态已买入（状态0），没买入(状态1)，然后还能细分状态（持有->卖出）阶段（动态规划）。

双指针

class Solution {
    public int maxProfit(int[] prices) {
        int len=prices.length;
        if(len<2) return 0;
        int slow = 0;
        int res = 0;
        for(int fast=1;fast<len;fast++){
            if(prices[slow]>prices[fast]){
                slow=fast;// 下标fast找到的值才是最小的
            }else{
                res=Math.max(res,prices[fast]-prices[slow]);// 记录最佳时机
            }
        }
        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

贪心

class Solution {
    public int maxProfit(int[] prices) {  
        int len = prices.length;  
        if (len < 2) return 0;  
        int min = prices[0]; 
        int max = 0;// 这里的最大值是记录最佳时机的最大值！
        for (int num : prices) {  
            min = Math.min(min, num);  
            int temp = num - min; // 遍历记录  
            max = Math.max(max, temp);  
        }  
        return max;  
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

动态规划

class Solution {
    public int maxProfit(int[] prices) {
        int len=prices.length;
        if(len<2) return 0;
        // 二列，已买入（状态0），没买入(状态1)
        int[][] dp = new int[len][2];
        // 初始化
        // 已买入后存在：1.继续持有 2.卖出
        // 没买入后存在：1.保留成本 2.买入
        dp[0][0]=0;
        dp[0][1]=-prices[0];// 第一天就买入（假设值）
        // 开始递推（找状态）
        for(int i = 1;i<len;i++){
            dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);// 继续持有 | 卖出
            dp[i][1]=Math.max(dp[i-1][1],-prices[i]);// 保留成本 | 买入
        }
        // 返回最后的卖出，或者根本没买入过（假设股票是5,4,3,2,1）(最佳时机就是不买入：0)
        return dp[len-1][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20