一道关于股票的算法题，和121 & 123 类似

楼主近期面试了 一家公司， 面试题是这样的： 每天最多买一次，每天也最多卖一次，买一次或者卖一次只能买一股或者卖一股，求最大利润。
这道题和LC 121 和 123 很像，但是可以同时持有多股。注意的是，给出的array 代表的是一只股票不同天的价格。比如[1,2,3,4]。
有会的同学能分享下思路吗？ 谢谢～～～

1. int maximumProfit(vector<int>& prices) {
   
2.     priority_queue<pair<int, int>> Q;
   
3.    
   
4.     int profit = 0, n = prices.size();
   
5.    
   
6.     unordered_set<int> visited;
   
7.    
   
8.     for (int i = 0; i < n; i++) {
   
9.         Q.push(make_pair(-prices[i], i));
   
10.     }
    
11.    
    
12.     for (int i = n - 1; i >= 0; i--) {
    
13.         auto [price, index] = Q.top();
    
14.         
    
15.         if (index < i && -price < prices[i] && visited.count(index) == 0) {
    
16.             profit += prices[i] + price; Q.pop();
    
17.             visited.insert(index);
    
18.         }
    
19.     }
    
20.    
    
21.     return profit;
    
22. }
    

复制代码

楼主试试看看对不对?

补充内容 (2021-3-16 00:31):
这个写的不太对。大家别参考了。

我不太确定完全理解了题目的意思，我理解的意思大概是每天都可以买或者卖，可以买很多次但是只卖一次。这样理解对吗？
比如说
{1, 2, 3, 4, 1, 5, 4}
买 买 买 买 买 卖 买

这样的最终受益是 4+3+2+1+4 = 14

1. 
   
2. [i]#include <iostream>
   
3. #include <vector>
   
4. using namespace std;
   
5. 
   
6. int maxProfit(vector<int> input)
   
7. {
   
8.     int res = 0;
   
9.     for(int i=input.size()-1, mx=input.back(); i>=0; --i)
   
10.     {
    
11.         mx = max(mx, input[i]);
    
12.         res += mx-input[i];
    
13.     }
    
14.     return res;
    
15. }
    
16. int main()
    
17. {
    
18.     cout << maxProfit({1,2,3,4,1,5,4}) << endl;
    
19. 
    
20.     return 0;
    
21. }[i][i]
    

复制代码

从后往前找最大值，用当前值和最大值的差值作为收益，直到所有的值都访问一次。
这样理解不知道对不对。[/i][/i][/i]

感觉是不是贪心算法。按price的大小把index存到最大堆，然后从大到小开始遍历，然后找到坐标在Q.top()左边的最小的price，然后计算profit。

比如说 prices 是 [4, 2, 7, 100, 3]， 那么heap里存的就是 [3, 2, 0, 4, 1]。

i = 3, prices[3] = 100， 左边比它小的最小的price是2， 所以 profit = 100 - 2。然后记录一下 2 已经被用过了。然后Q.pop()，处理下一个。
i = 2, prices[2] = 7, 左边比它小的最小的还没用过的price是4， 所以 profit += 7 - 4。

乍看以为是122，仔细一想还不一样。感觉贪心可解。看来股票题的变种很多呀。

这是不是加油站的变种题呢？

14417335 发表于 2021-3-16 00:22
这是不是加油站的变种题呢？

加油站 是哪道题

wisdompeak2 发表于 2021-3-15 14:44
乍看以为是122，仔细一想还不一样。感觉贪心可解。看来股票题的变种很多呀。

贪心算法，能不能大概分享下思路，谢谢～～

喜刷刷_Go 发表于 2021-3-15 12:33
加油站 是哪道题

871

那么DP【第几天】【拥有多少股】= 最多的价值

14417335 发表于 2021-3-16 02:36
871

那么DP【第几天】【拥有多少股】= 最多的价值

谢谢，我看看～～