【leetcode】121. 买卖股票的最佳时机
题目内容
思路分析
本题看起来很简单，但是自己做就是怎么都做不出来...自闭ing😶
本题共有两种思路，动态规划（方法一和方法二）和单调栈（方法三）。
方法一：动态规划
选用动态规划的原因：
包含了重叠的子问题，买入和卖出股票的最佳时机是由之前的状态决定的，而之前的状态又是由更早的状态决定的。
设max_profit为从第0天到第i天参与股市，可获得的最大利润，则可写出状态转移方程max_profit[i] = max(max_profit[i-1], prices[i] - min_price)，边界条件为max_profit[i] = 0 , i = 0。最后返回max_profit[-1]即可，其意义为从第0天到最后一天参与股市，可获得的最大利润。
方法二：动态规划优化/拟人
由于方法一中的状态转移方程其实就是不断地与之前的最大利润做对比，因此我们不必花O(N)的空间去维护动态规划的状态数组，只需使用一个变量去维护当前能获得的最大利润即可。
此方法还可如此理解或想出（拟人）：炒股的人每天都在想”我要是以之前的最低价格买入的就好了“。因此使用每天的价格减去之前的最低价格，并维护每天能获得的最大利润即可。
方法三：单调栈
方法三使用了单调栈。个人认为这个题没有必要使用单调栈，本题的题解所用单调栈感觉其实就是维护了个最小价格，最终还是将所有元素的最大利润都遍历了一遍。
但是单调栈这种方法确实很妙，适用于一些其他场景。（以下来自知乎-刷题笔记6（浅谈单调栈））
例如以下题目：
一个数组，返回一个大小相同的数组。返回的数组的第i个位置的值应当是，对于原数组中的第i个元素，至少往右走多少步，才能遇到一个比自己大的元素（如果之后没有比自己大的元素，或者已经是最后一个元素，则在返回数组的对应位置放上-1）
例子：
输入：5,3,1,2,4
输出：-1,3,1,1,-1
解释：对于第0个数字5，之后没有比它更大的数字，因此是-1，对于第1个数字3，需要走3步才能达到4（第一个比3大的元素），对于第2和第3个数字，都只需要走1步，就可以遇到比自己大的元素。对于最后一个数字4，因为之后没有更多的元素，所以是-1。
这个题要用暴力法做的话复杂度将达到O(N^2)，即第一层循环是遍历每个数字，第二层遍历是寻找该数字右侧的第一个比自己大的元素。
而若是使用单调栈法，维护一个单调递减的栈（栈底元素大，栈顶元素小），栈内存储数组的索引。只需遍历每个数字num，对比其与栈顶索引对应的数字x，若num > x，则出栈栈顶元素，直到不满足num > x；若num < x，则证明num小于栈中的任何一个索引对应的数（单调栈的意义所在）。对比完后，数字都需进行入栈，等待自己的那个TA❤🤣。
通过这种方法，我们就在O(N)的时间复杂度下解出了题目。（代码实现等详见知乎链接）
代码
#include <vector>
#include <limits>
using namespace std;
class Solution {
public:
// 官方解法，按人的思维想，每天都想“我要是在最低点买入的就好了”
// 然后比较按最低点买入的利润和之前的最大利润谁大，更新最大利润
// 此方法是动态规划法的优化，不需要维护动态规划状态数组
// 时间复杂度O(N)，空间复杂度O(1)
int maxProfit1(vector<int>& prices) {
int min_price{ INT_MAX }, max_profit{ 0 };
for (int price : prices) {
max_profit = max(max_profit, price - min_price);
min_price = min(price, min_price);
}
return max_profit;
}
// 单调栈法 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/c-li-yong-shao-bing-wei-hu-yi-ge-dan-diao-zhan-tu-/
// 时间复杂度O(N)，空间复杂度O(N)
int maxProfit2(vector<int>& prices) {
vector<int> s;
int max_profit{ 0 };
prices.push_back(-1); // 加入哨兵，遇到哨兵时弹出栈内所有非底元素并计算利润
for (int price : prices) {
// 要调用font()和back()，则size()不能为0
// 当价格小于栈顶元素或价格为哨兵(证明遍历结束)时，弹出栈顶元素并更新最大利润
// 这里也利用了条件与里判断第一个条件若为false则会直接退出，不会进行第二个条
// 件判断的特点
while (s.size() != 0 && (price < s.back() or price == -1)) {
max_profit = max(s.back() - s.front(), max_profit);
s.pop_back();
}
s.push_back(price);
}
return max_profit;
}
// 动态规划法
// 状态转移方程：
// max_profit[i] = max(max_profit[i-1], prices[i] - min_price)
// 边界条件：
// max_profit[i] = 0 , i = 0
// 时间复杂度O(N)，空间复杂度O(N)
int maxProfit(vector<int>& prices) {
unsigned long n{ prices.size() };
if (n == 0) return 0;
vector<int> max_profit(prices.size()); // 初始化，容器内容为prices.size()个0
int min_price{ prices[0] };
for (int i = 1; i < n; ++i) { // 注意到从下标1开始遍历
max_profit[i] = max(max_profit[i - 1], prices[i] - min_price);
min_price = min(prices[i], min_price);
}
return max_profit[n - 1];
}
};
int main() {
Solution s;
vector<int> input{ 7,1,5,3,6,4 };
int output;
output = s.maxProfit(input);
return output;
}
收获
- 在查阅单调栈资料的过程中，发现C++有栈这个功能。如：
stack<int> monoStack。翻了C++ primer后了解了一些和C++栈有关的知识。- stack是C++的顺序容器适配器，它能接受一个除array和forward_list外的一个顺序容器，使其操作起来像stack一样。
- 它默认基于deque实现，支持pop()，push()，top()等操作。
- 这个动态规划比较简单，算是入门了动态规划。
- 了解到了“拟人”的这种思维方式，应该以后会用的上。
- 通过看多种解的方式，了解到了单调栈这种算法，甚至还相当于做了一道单调栈的题目。