【leetcode】剑指 Offer 63. 股票的最大利润

Bertha 。 2022-10-16 06:27 127阅读 0赞

### 剑指 Offer 63. 股票的最大利润 ###

*  题目难度：中等
 *  方法一：动态规划

> 链接：[https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/][https_leetcode-cn.com_problems_gu-piao-de-zui-da-li-run-lcof]  
> 来源：力扣（LeetCode）图解算法数据结构

# 题目难度：中等 #

假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

示例 1：

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

示例 2：

输入: [7,6,4,3,1]
    输出: 0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

限制：

0 <= 数组长度 <= 10^5

模板

class Solution {
        
        public int maxProfit(int[] prices) {
        
    
        }
    }

# 方法一：动态规划 #

**解题思路：**

动态规划解析：三部曲

*  **定义状态**： 设动态规划列表  d p dp dp ， d p \[ i \] dp\[i\] dp\[i\] 代表以  p r i c e s \[ i \] prices\[i\] prices\[i\] 为结尾的子数组的最大利润（以下简称为 前  i i i 日的最大利润 ）。
 *  **转移方程**： 由于题目限定 “`买卖该股票一次`” ，因此前  i i i 日最大利润  d p \[ i \] dp\[i\] dp\[i\] 等于 前  i − 1 i−1 i−1 日最大利润  d p \[ i − 1 \] dp\[i−1\] dp\[i−1\] 和 第  i i i 日卖出的最大利润 中的最大值  
     d p \[ i \] = m a x ( d p \[ i − 1 \] , p r i c e s \[ i \] − m i n ( p r i c e s \[ 0 : i \] ) ) dp\[i\]=max(dp\[i−1\],prices\[i\]−min(prices\[0:i\])) dp\[i\]=max(dp\[i−1\],prices\[i\]−min(prices\[0:i\])) ↑ \\uparrow ↑ 前 i 日 最 大 利 润 = max ⁡ ( 前 ( i − 1 ) 日 最 大 利 润 , 第 i 日 价 格 − 前 i 日 最 低 价 格 ) 前i日最大利润=\\max(前(i−1)日最大利润,第i日价格−前i日最低价格) 前i日最大利润=max(前(i−1)日最大利润,第i日价格−前i日最低价格)
 *  **初始状态**： d p \[ 0 \] = 0 dp\[0\]=0 dp\[0\]=0 ，即首日利润为  0 0 0 ； 。
 *  **返回值**： d p \[ n − 1 \] dp\[n−1\] dp\[n−1\] ，其中  n n n 为  d p dp dp 列表长度。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70_pic_center]  
时间复杂度降低：

*  前  i i i 日的最低价格  min ⁡ ( p r i c e s \[ 0 : i \] ) \\min(prices\[0:i\]) min(prices\[0:i\]) 时间复杂度为  O ( i ) O(i) O(i) 。而在遍历  p r i c e s prices prices 时，可以借助一个变量（记为成本  c o s t cost cost ）每日更新最低价格。优化后的转移方程为：  
     d p \[ i \] = max ⁡ ( d p \[ i − 1 \] , p r i c e s \[ i \] − min ⁡ ( c o s t , p r i c e s \[ i \] ) dp\[i\]=\\max(dp\[i−1\],prices\[i\]−\\min(cost,prices\[i\]) dp\[i\]=max(dp\[i−1\],prices\[i\]−min(cost,prices\[i\])

空间复杂度降低：

*  由于  d p \[ i \] dp\[i\] dp\[i\] 只与  d p \[ i − 1 \] , p r i c e s \[ i \] , c o s t dp\[i−1\] , prices\[i\] , cost dp\[i−1\],prices\[i\],cost 相关，因此可使用一个变量（记为利润  p r o f i t profit profit ）代替  d p dp dp 列表。优化后的转移方程为  
     p r o f i t = max ⁡ ( p r o f i t , p r i c e s \[ i \] − min ⁡ ( c o s t , p r i c e s \[ i \] ) profit=\\max(profit,prices\[i\]−\\min(cost,prices\[i\]) profit=max(profit,prices\[i\]−min(cost,prices\[i\])

复杂度分析：

*  时间复杂度  O ( N ) O(N) O(N) ： 其中  N N N 为  p r i c e s prices prices 列表长度，动态规划需遍历  p r i c e s prices prices 。
 *  空间复杂度  O ( 1 ) O(1) O(1) ： 变量  c o s t cost cost 和  p r o f i t profit profit 使用常数大小的额外空间。

思路 ：

1、状态定义： `F[n]` 表示 `prices` 中 `0-n` 下标的子数组的最大利润

2、转移方程：

*   前 n 天 的 最 大 利 润 = max ⁡ ( 前 n − 1 天 的 最 大 利 润 ， 第 n 天 的 价 格 − 前 n 天 的 最 低 价 格 ) 前 n 天的最大利润 = \\max(前 n-1 天的最大利润，第 n 天的价格 - 前 n 天的最低价格) 前n天的最大利润=max(前n−1天的最大利润，第n天的价格−前n天的最低价格)  
     F \[ n \] = m a x ( F ( n − 1 ) , m i n ( p r i c e s \[ n \] , m i n C o s t ) ) F\[n\] = max(F(n-1), min(prices\[n\], minCost)) F\[n\]=max(F(n−1),min(prices\[n\],minCost))

3、初始状态： `F[0] = 0`

4、其中只需要记录 `minCost` 和 `F(n-1)` 这两个内容即可，不需要留存之前的动态规划记录，进而将空间复杂度从`O(n)`降低到了`O(1)`

class Solution {
        
        public int maxProfit(int[] prices) {
        
            if (prices.length == 0) return 0; 
    
            int[] dp = new int[prices.length]; 
            dp[0] = 0; // 初始化状态
            int minCost = prices[0];
            for (int i = 1; i < prices.length; i++) {
        
                minCost = Math.min(minCost, prices[i]);
                dp[i] = Math.max(dp[i - 1], prices[i] - minCost); // 定义转移方程
            }
            return dp[prices.length - 1];
        }
    }

优化：

class Solution {
        
        public int maxProfit(int[] prices) {
        
            if (prices.length == 0) return 0;
    
            int maxProfit = 0;
            int minCost = prices[0];
            for (int i = 1; i < prices.length; i++) {
        
                minCost = Math.min(minCost, prices[i]);
                maxProfit = Math.max(maxProfit, prices[i] - minCost);
            }
            return maxProfit;
        }
    }

[https_leetcode-cn.com_problems_gu-piao-de-zui-da-li-run-lcof]: https://leetcode-cn.com/problems/gu-piao-de-zui-da-li-run-lcof/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNzI3MDk1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221014/c68c7db093bb4381a9e6b28a5b98f751.png