[剑指offer]面试题第[63]题[Leetcode][第121题][JAVA][买卖股票的最佳时机][动态规划][暴力]

心已赠人 2023-02-25 02:25 13阅读 0赞

#### 【问题描述】\[简单\] ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]

#### 【解答思路】 ####

###### 1. 暴力 ######

![在这里插入图片描述][20200710113320874.png]  
**时间复杂度：O(N^2) 空间复杂度：O(1)**  
![在这里插入图片描述][20200710113346834.png]

public class Solution { 
        public int maxProfit(int prices[]) { 
            int maxprofit = 0;
            for (int i = 0; i < prices.length - 1; i++) { 
                for (int j = i + 1; j < prices.length; j++) { 
                    int profit = prices[j] - prices[i];
                    if (profit > maxprofit)
                        maxprofit = profit;
                }
            }
            return maxprofit;
        }
    }

###### 2. 动态规划/哨兵思想 ######

**解释一**![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]  
**时间复杂度：O(N) 空间复杂度：O(1)**  
![在这里插入图片描述][20200710113427586.png]

public class Solution { 
        public int maxProfit(int prices[]) { 
            int minprice = Integer.MAX_VALUE;
            int maxprofit = 0;
            for (int i = 0; i < prices.length; i++) { 
                if (prices[i] < minprice)
                    minprice = prices[i];
                else if (prices[i] - minprice > maxprofit)
                    maxprofit = prices[i] - minprice;
            }
            return maxprofit;
        }
    }

**解释二**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]

public int maxProfit(int[] prices) { 
            if(prices.length == 0) 
                return 0;
             int max=0;
             int min=prices[0];
             int[] dp=new int[prices.length];
             for(int i=1;i<prices.length;i++){ 
                 min=Math.min(prices[i],min);  //一直找最小的值
                 dp[i]=Math.max(dp[i-1],prices[i]-min);
             }
             return dp[prices.length-1];
        
        }

class Solution { 
        public int maxProfit(int[] prices) { 
            int cost = Integer.MAX_VALUE, profit = 0;
            for(int price : prices) { 
                cost = Math.min(cost, price);
                profit = Math.max(profit, price - cost);
            }
            return profit;
        }
    }

#### 【总结】 ####

###### 1.动态规划流程 ######

第 1 步：设计状态  
第 2 步：状态转移方程  
第 3 步：考虑初始化  
第 4 步：考虑输出  
第 5 步：考虑是否可以状态压缩

###### 2. 暴力逐步优化 思想要到位 ######

转载链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/121-mai-mai-gu-piao-de-zui-jia-shi-ji-by-leetcode-/

参考链接：https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/solution/mian-shi-ti-63-gu-piao-de-zui-da-li-run-dong-tai-2/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: /images/20230209/4a7a3a5fc17f44f5927a25e515dcc337.png
[20200710113320874.png]: /images/20230209/455cfa623fe146d4938cd5f7086509e4.png
[20200710113346834.png]: /images/20230209/3b1309ee5b3d42e481fd2332f1022780.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: /images/20230209/9c2aa15d6b014ffbbdec653163824748.png
[20200710113427586.png]: /images/20230209/859d7e39272d4fc28c2f4adc881fff7c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: /images/20230209/f5bef76527634cdeb0be706ef0919fc4.png