[LeetCode] Best Time to Buy and Sell Stock 买卖股票的最佳时间

Category	Difficulty	Likes	Dislikes
algorithms	Easy (55.00%)	1235	-

TagsCompanies

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:

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

解法一 暴力破解

先写个暴力的，看看对题目的理解对不对。用两个循环，外层循环表示买入时候的价格，内层循环表示卖出时候的价格，遍历所有的情况，期间更新最大的收益。

1 int maxProfit(vector<int>& prices) {
2     int maxProfit = 0;
3     for (int i = 0; i < prices.size(); i++) {
4         for (int j = i + 1; j <prices.size(); j++) {
5             maxProfit = max(maxProfit, prices[j] - prices[i]);
6         }
7     }
8     return maxProfit;
9 }

200个case过了199个，还有个超时，说明暴力的算法没问题，需要效率优化。

解法二 双指针法

 这种数组问题的优化，经常就是考虑双指针的方法，从而使得两层循环变成一层。用两个指针， buy 表示第几天买入，sell 表示第几天卖出，开始 buy,sell都指向 0，表示不操作。然后sell往后移，

若prices[sell]  < prices[buy],则将buy指向sell当前位置（buy = sell）,否则计算当前股票买卖收益，并和之前计算的收益比较，取最大的值。

 1 //双指针法求股票买卖最佳时机问题
 2    
 3     int maxProfit_doublePtr(vector<int>& prices)
 4     {
 5         int buy=0,sell=0;
 6         int maxProfit = 0;
 7         for(;sell<prices.size();++sell)
 8         {
 9             if(prices[sell]<prices[buy])
10             {
11                 buy = sell;
12             }
13             else
14             {
15                 maxProfit = max(maxProfit,prices[sell]-prices[buy]);
16             }
17         }
18         return maxProfit;
19     }

解法三 动态规划

将求股票买卖最大收益问题转化为求数组的最子序列最大和。然后使用动态规划求数组的最子序列最大和。

 1 //将股票买卖时机问题转化为 数组的最子序列最大和问题
 2     int maxProfit_dp(vector<int>& prices)
 3     {
 4         if(prices.empty())
 5         {
 6             return 0; 
 7         }
 8         int front  = prices[0];
 9         prices[0] = 0;
10         for(int i = 1;i<prices.size();++i)
11         {
12             int tmp = prices[i];
13             prices[i] = prices[i] - front;
14             front = tmp;
15         }
16 
17         return maxSubArrySum(prices);
18     }
19     //数组的子序列最大和
20     int maxSubArrySum(vector<int>& prices)
21     {
22         vector<int> dp (prices); //dp[i] 表示以prices[i]结尾的和最的子序列
23         int res = dp[0];
24         for(int i = 1;i<prices.size();++i)
25         {
26             dp[i] = dp[i-1]<0?prices[i]:dp[i-1]+prices[i];
27             res = max(res,dp[i]);
28         }
29         return res; 
30     }

总结：这道题虽然是比较简单的，但是双指针的用法还是经常见的，值得好好总结。另外解法三对问题的转换很巧妙。