题目
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4] 输出：5 解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。 注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
示例 2：
输入：prices = [7,6,4,3,1] 输出：0 解释：在这种情况下, 没有交易完成, 所以最大利润为 0。
解题
方法一：贪心
因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。
class Solution { public: int maxProfit(vector<int>& prices) { int low=INT_MAX; int res=0; for(int i=0;i<prices.size();i++){ low=min(low,prices[i]); res=max(res,prices[i]-low); } return res; } };
方法二：动态规划
dp[i][0]表示第i天不持有股票
dp[i][1]表示第i天持有股票
class Solution { public: int maxProfit(vector<int>& prices) { int n=prices.size(); if(n<=1) return 0; vector<vector<int>> dp(n,vector<int>(2)); 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],-prices[i]); } return dp[n-1][0]; } };
这样子代表只能买卖一次
dp[i][1]=max(dp[i-1][1],-prices[i]);
而代表可以买卖多次
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
这道题中dp[i][1]由于只能买一次dp[i][1]=max(dp[i-1][1],-prices[i]);这个dp[i][1]相当于自始至终维护的是购买股票的最小亏损，因为只买一次，一定是负的，相当于选取一个最小的价格买入。
方法三：单调栈
class Solution { public: int maxProfit(vector<int>& prices) { int res=0; vector<int> stack; prices.push_back(-1);//加入哨兵 for (int i = 0; i < prices.size(); ++ i){ while (!stack.empty()&&stack.back() > prices[i]){ //维护单调栈 res=max(res,stack.back()-stack.front());// 维护最大值 stack.pop_back(); } stack.push_back(prices[i]); } return res; } };
当prices[i]比单调栈顶小的时候，stack.pop_back()，弹出栈顶大的数，是为了使得较小的数，放在单调栈底。
‘每次弹出的时候都要维护一下最大值res。
如果prices是递增的，那么单调栈就依次堆叠，但是出现比较小的数，会将栈顶弹出，并且维护最大值。
因为新的price[i]比较小，不能用老的栈顶(大的值)去减去新的price[i],所以把老的栈顶(大的值)弹出。
当prices遍历完后，最后利用哨兵(-1)，对单调栈内剩下的进行最大值维护。
