股票系列

121. 买卖股票的最佳时机【简单】

题目意思：只能买入一次，卖出一次，最大利润

思路二：贪心

时间复杂度：O(n)

空间复杂度：O(1)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = INT_MAX;
        int maxProfit = 0;
        for (int price : prices) {   
            minPrice = min(minPrice, price);              // 动态更新最小价格
            maxProfit = max(maxProfit, price - minPrice);     
        }
        return maxProfit;
    }
};

思路三：动态规划

五部曲：

确定dp数组以及下标含义：

dp[i][0]表示第i天交易完后手里没有股票的最大利润

dp[i][1]表示第i天交易完后手里持有股票的最大利润

确定递推公式

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);

dp[i][1] = max(dp[i-1][i], -prices[i]);

初始化

dp[i][0] = 0;

dp[i][1] = -prices[0];

时间复杂度：O(n)

空间复杂度：O(n)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int dp[n][2];
        //初始化
        dp[0][0] = 0;           //第0天不持有股票的最大利润
        dp[0][1] = -prices[0];  //第0天持有股票的最大利润
        for (int i = 1; i < n; i++) {
            //第i天不持有股票的maxProfit = max(第i-1天不持有股票的maxProfit，第i-1天持有但第i天卖出时的maxProfit)
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);  
            //第i天持有股票的maxProfit = max(第i-1天持有股票的maxProfit，今天刚买入股票时的maxProfit)
            dp[i][1] = max(dp[i-1][1], -prices[i]);            
        }
        return dp[n-1][0];
    }
};

空间优化：

注意到上面的状态转移方程中，每一天的状态只与前一天的状态有关，而与更早的状态都无关，因此我们不必存储这些无关的状态，只需要将 dp[i-1][0]和 dp[i-1][1]存放在两个变量中，通过它们计算出 dp[i][0]和 dp[i][1]并存回对应的变量，以便于第 i+1天的状态转移即可。

空间复杂度：O(1)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int sell = 0;
        int buy = -prices[0];
        for (int i = 1; i < n; ++i) {
            sell = max(sell, buy + prices[i]);
            buy = max(buy, -prices[i]);
        }
        return sell;
    }
};

122. 买卖股票的最佳时机 II【中等】

题目意思：

只有一只股票！

当前只有买股票或者买股票的操作

思路：把每一题的股价描点画成折线图，求所有上升线段的累加；借鉴376题

贪心：

时间复杂度：O(n)

空间复杂度：O(1)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
    for(int i = 1; i < prices.size(); i++){
            if(prices[i] - prices[i-1] > 0)  
                res += prices[i] - prices[i-1];
        }
        return res;
    }
};

思路二：动态规划

时间复杂度：O(n)

空间复杂度：O(n)

五部曲：

确定dp数组以及下标含义：

dp[i][0]表示第i天交易完后手里没有股票的最大利润

dp[i][1]表示第i天交易完后手里持有股票的最大利润

确定递推公式

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);

dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);

初始化

dp[i][0] = 0;

dp[i][1] = -prices[0];

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int dp[n][2];
        dp[0][0] = 0;            
        dp[0][1] = -prices[0];   
        for(int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }
        return dp[n-1][0];
    }
};

空间优化：

空间复杂度：O(1)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int sell = 0;
        int buy = -prices[0];
        for (int i = 1; i < n; ++i) {
            sell = max(sell, buy +prices[i]);
            buy = max(buy, sell -prices[i]);
        }
        return sell;
    }
};

123. 买卖股票的最佳时机 III【困难】

思路：动态规划

时间复杂度：O(n)

空间复杂度：O(1)

看官方答案，能看懂

未进行过任何操作

只进行过一次买操作

进行了一次买操作和一次卖操作，即完成了一笔交易

在完成了一笔交易的前提下，进行了第二次买操作

完成了全部两笔交易

buy1：

在第i天不进行任何操作，保持原状态

在未进行任何操作的前提下以prices[i]的价格买入股票

buy1 = max(buy1, -prices[i]);

sell1：

在第i天不进行任何操作

在只进行过一次买操作的前提下，以prices[i]的价格卖出股票

sell1 = mamx(sell1, buy1+prices[i]);

  class Solution {
  public:
      int maxProfit(vector<int>& prices) {
          //dp初始化
      int buy1 = -prices[0];
          int sell1 = 0;
          int buy2 = -prices[0];
          int sell2 = 0;
          for(int i = 1; i < prices.size(); ++i){
              //状态转移函数
              buy1 = max(buy1, -prices[i]);
              sell1 = max(sell1, buy1+prices[i]);
              buy2 = max(buy2, sell1-prices[i]);
              sell2 = max(sell2, buy2+prices[i]);
          }
          return sell2;
      }
  };

没进行空间优化之前是下面这样子：

没有操作

第一次买入

第一次卖出

第二次买入

第二次卖出

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() == 0) return 0;
        vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
        dp[0][1] = -prices[0];
        dp[0][3] = -prices[0];
        for (int i = 1; i < prices.size(); i++) {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
            dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
            dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
            dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
        }
        return dp[prices.size() - 1][4];
    }
};

188. 买卖股票的最佳时机 IV【困难】

方法：动态规划

确定dp下标以及含义：

buy[i][j]：表示对于数组price[0~i]中的价格而言，恰好进行完j笔交易，并且当前手上持有一只股票，这时的最大利润

sell[i][j]：表示恰好进行完j笔交易，并且当前手上不持有股票，这时的最大利润

确定状态转移函数

buy[i][j] = max(buy[i-1][j], sell[i-1][j] - prices[i]);

``sell[i][j] = max(sell[i-1][j], buy[i-1][j-1] + prices[i]);`

dp初始化

buy[0][0] = -prices[0];

sell[0][0] = 0;

buy[0][1...k]是不合法的操作，设置一个不合理的值

sell[0][1...k]是不合法的操作

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.empty())  return 0;
        int n = prices.size();
        k = min(k, n / 2);   //n天最多完成 n/2笔交易  这行相当于剪枝，不加也行
        vector<vector<int>> buy(n, vector<int>(k + 1));
        vector<vector<int>> sell(n, vector<int>(k + 1));
        //初始化
        buy[0][0] = -prices[0];
        sell[0][0] = 0;
        for (int i = 1; i <= k; ++i) {
            buy[0][i] = sell[0][i] = INT_MIN / 2;  //为什么除2，因为后面有+操作，就会超出int值
        }
        for (int i = 1; i < n; ++i) {
            buy[i][0] = max(buy[i - 1][0], sell[i - 1][0] - prices[i]);
            for (int j = 1; j <= k; ++j) {
                buy[i][j] = max(buy[i - 1][j], sell[i - 1][j] - prices[i]);
                sell[i][j] = max(sell[i - 1][j], buy[i - 1][j - 1] + prices[i]);   
            }
        }
    //为什么返回这个？  最多完成k笔交易，但不是完成k笔交易时max
        return *max_element(sell[n - 1].begin(), sell[n - 1].end());
    }
};

空间优化：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.empty())  return 0;
        int n = prices.size();
        k = min(k, n / 2);
        vector<int> buy(k + 1);
        vector<int> sell(k + 1);
        buy[0] = -prices[0];
        sell[0] = 0;
        for (int i = 1; i <= k; ++i) {
            buy[i] = sell[i] = INT_MIN / 2;
        }
        for (int i = 1; i < n; ++i) {
            buy[0] = max(buy[0], sell[0] - prices[i]);
            for (int j = 1; j <= k; ++j) {
                buy[j] = max(buy[j], sell[j] - prices[i]);
                sell[j] = max(sell[j], buy[j-1] + prices[i]);   
            }
        }
        return *max_element(sell.begin(), sell.end());
    }
};

时间复杂度：O(n * min(n,k))

空间复杂度：O(min(n,k))

309. 最佳买卖股票时机含冷冻期【中等】

思路：动态规划

1、确定dp数组及其含义

目前持有一只股票，对应的累加最大收益记为f[i][0]

目前不持有任何股票，并给处于冷冻期中，对应的累计最大收益记为f[i][1]

目前不持有任何股票，并且不处于冷冻期中，对应的累计最大收益记为f[i][2]

2、确定状态转移函数

f[i][0] = max(f[i-1][0], f[i-1][2] - prices[i]);

f[i][1] = f[i-1][0] + prices[i];

f[i][2] = max(f[i-1][1], f[i-1][2]);

最终最大利润为：max(f[n-1][1], f[n-1][2])

3、初始化

f[0][0] = -prices[0];

f[0][1] = 0;

f[0][2] = 0;

时间复杂度：O(n)

空间复杂度：O(n)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        int n = prices.size();
        // f[i][0]: 手上持有股票的最大收益
        // f[i][1]: 手上不持有股票，并且处于冷冻期中的累计最大收益
        // f[i][2]: 手上不持有股票，并且不在冷冻期中的累计最大收益
        vector<vector<int>> f(n, vector<int>(3));
        f[0][0] = -prices[0];
        for (int i = 1; i < n; ++i) {
            f[i][0] = max(f[i-1][0], f[i-1][2] - prices[i]);
            f[i][1] = f[i-1][0] + prices[i];
            f[i][2] = max(f[i-1][1], f[i-1][2]);
        }
        return max(f[n-1][1], f[n-1][2]);
    }
};

空间优化：

空间复杂度：O(1)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        int n = prices.size();
        int f0 = -prices[0];
        int f1 = 0;
        int f2 = 0;
        for (int i = 1; i < n; ++i) {
            int newf0 = max(f0, f2 - prices[i]);
            int newf1 = f0 + prices[i];
            int newf2 = max(f1, f2);
            f0 = newf0;
            f1 = newf1;
            f2 = newf2;
        }
        return max(f1, f2);
    }
};

714. 买卖股票的最佳时机含手续费【中等】

思路一：贪心

时间复杂度：O(n)

空间复杂度：O(1)

我们在做收获利润操作的时候其实有三种情况：

情况一：收获利润的这一天并不是收获利润区间里的最后一天（不是真正的卖出，相当于持有股票），所以后面要继续收获利润。

情况二：前一天是收获利润区间里的最后一天（相当于真正的卖出了），今天要重新记录最小价格了。

情况三：不作操作，保持原有状态（买入，卖出，不买不卖）

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int res = 0;
        int minPrice = prices[0]; // 记录最低价格
        for (int i = 1; i < prices.size(); i++) {
            // 情况二：相当于买入
            if (prices[i] < minPrice)  minPrice = prices[i];
            // 情况三：保持原有状态（因为此时买则不便宜，卖则亏本）
            //if (prices[i] >= minPrice && prices[i] <= minPrice + fee) {
            //    continue;
            //}
            // 计算利润，可能有多次计算利润，最后一次计算利润才是真正意义的卖出
            if (prices[i] > minPrice + fee) {
                res += prices[i] - minPrice - fee;
                minPrice = prices[i] - fee; // 情况一，这一步很关键
            }
        }
        return res;
    }
};

当我们卖出一支股票时，我们就立即获得了以相同价格并且免除手续费买入一支股票的权利

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int buy = prices[0] + fee;
        int profit = 0;
        for (int i = 1; i < prices.size(); ++i) {
            if (prices[i] + fee < buy) {   //更新买入价
                buy = prices[i] + fee;
            }
            else if (prices[i] > buy) {    //收集利润
                profit += prices[i] - buy;
                buy = prices[i];
            }
        }
        return profit;
    }
};

思路二：动态规划

1、dp及其下标含义

dp[i][0]表示第i天交易完后手里没有股票的最大利润

dp[i][1]表示第i天交易完后手里持有一只股票的最大利润

2、转移函数

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee);

dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);

3、初始化

dp[0][0] = 0;

dp[0][1] = -prices[0];

时间复杂度：O(n)

空间复杂度：O(n)

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2));
        //初始化
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }
        return dp[n-1][0];
    }
};

空间优化

空间复杂度：O(1)

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        //初始化
        int sell = 0;
        int buy = -prices[0];
        //为什么从1开始，因为0已经初始化了 
        for (int i = 1; i < n; ++i) {
            sell = max(sell, buy + prices[i] - fee);
            buy = max(buy, sell - prices[i]);
        }
        return sell;
    }
};

LeetCode股票系列

股票系列

121. 买卖股票的最佳时机【简单】

122. 买卖股票的最佳时机 II【中等】

123. 买卖股票的最佳时机 III【困难】

188. 买卖股票的最佳时机 IV【困难】

309. 最佳买卖股票时机含冷冻期【中等】

714. 买卖股票的最佳时机含手续费【中等】

热门文章

最新文章

相关电子书