股票买卖系列题目
- 121. 买卖股票的最佳时机
- 122. 买卖股票的最佳时机 II
- 123. 买卖股票的最佳时机 III
- 188. 买卖股票的最佳时机 IV
- 309. 买卖股票的最佳时机含冷冻期
- 714. 买卖股票的最佳时机含手续费
核心思想：无论是买还是卖，我们都要让手里的钱最多，买则减少，卖则增多。我们这一次买还是卖只跟上一次买还是卖的状态有关。
针对 121 题，我们提出以下解答：
class Solution {
public:
int maxProfit(std::vector<int>& prices) {
int buy = INT_MIN;
int sell = 0;
for (int p : prices) {
buy = std::max(buy, 0 - p);//由于只进行一次买卖，所以买之前一定是没有进行过买的，所以是0-p
sell = std::max(sell, buy + p);
}
return sell;
}
};针对 122 题，我们提出以下解答：
class Solution {
public:
int maxProfit(std::vector<int>& prices) {
int buy = INT_MIN;
int sell = 0;
for (int p : prices) {
buy = std::max(buy, sell - p); //可以进行多次买卖，所以这里要用到前面的买卖状态
sell = std::max(sell, buy + p);
}
return sell;
}
};两者唯一的不同是 buy 一行中是否需要用到之前状态，若不需要，则是0-p，若需要，则是sell-p。这两者的区别在于题目是否允许多次买进卖出。
针对 123 题，本题要求最多只能进行两次交易，既然只让交易两次，那我们不妨将所有状态列举出来，再套用前面的思路。
class Solution {
public:
int maxProfit(const std::vector<int>& prices) {
int b1 = INT_MIN;
int b2 = INT_MIN;
int s1 = 0;
int s2 = 0;
for (int p : prices) {
b1 = std::max(b1, 0 - p); // First transaction buy
s1 = std::max(s1, b1 + p); // First transaction sell
b2 = std::max(b2, s1 - p); // Second transaction buy
s2 = std::max(s2, b2 + p); // Second transaction sell
}
return s2;
}
};针对 188 题，本题在 123 题的基础上，将交易次数限制在了K次，通过参数指定交易次数。
难道要写 2k 个参数吗？肯定不合适，我们选择使用数组来存储交易状态：
class Solution {
public:
int maxProfit(int k, const std::vector<int>& prices) {
k = std::min(k, static_cast<int>(prices.size()) / 2);
std::vector<int> buy(k + 1, INT_MIN);
std::vector<int> sell(k + 1, 0);
for (int p : prices) {
for (int i = 1; i <= k; ++i) {
buy[i] = std::max(buy[i], sell[i - 1] - p);
sell[i] = std::max(sell[i], buy[i] + p);
}
}
return sell.back();
}
};针对 309 题，题目新增要求：卖出股票后需要冷却一天才能新买股票。
class Solution {
public:
int maxProfit(const std::vector<int>& prices) {
int buy = INT_MIN;
int sell_pre = 0;
int sell = 0;
for (int p : prices) {
buy = std::max(buy, sell_pre - p); // Update the maximum buying state
int temp = sell; // Store the current sell state
sell = std::max(sell, buy + p); // Update the maximum selling state
sell_pre = temp; // Update sell_pre with the previous sell state
}
return sell;
}
};sell_pre总是保存上次卖出状态，buy 利用此来决定是否买入（buy = std::max(buy, sell_pre - p);）
针对 714 题，题目新增要求：买入股票时需要支付手续费，但卖出股票不需支付手续费。这样就很简单明了，在 buy 中加一个参数即可：
class Solution {
public:
int maxProfit(const std::vector<int>& prices, int fee) {
int buy = INT_MIN;
int sell = 0;
for (int p : prices) {
buy = std::max(buy, sell - p - fee);
sell = std::max(sell, buy + p);
}
return sell;
}
};综上看来，无论题目对我们做了什么限制，我们的核心都是围绕 buy 和 sell 进行的，buy 的含义是是否买入股票，因为我们追求的是最大利润，所以如果当日股票价格（price[i]）不合适，我们不会选择买入，比如对于7,1,5,3,6,4这个序列，遍历到第一天时，buy 初始化为 INT_MIN，而 0-buy 的值肯定大于此数，而遍历到第二天时，buy 值为-7，0-1 为-1，所以此时价格更优，更新买入价格，之后的遍历过程中不会有值比此更大，因此我们的 buy 值就一直确定为第二天买入，即buy=-1。而 sell 的含义是卖出，同样，遍历过程中会一直更新最佳卖出价，比如遍历到第一天时，buy 为-7，sell 为 0；遍历到第三天时，buy 为-1，此时 sell 会更新为 4。直到遍历结束，得出最终 sell 值为 5，即第二天买入，第五天卖出。
Comments NOTHING