LeetCode OJ是一个有一些面试算法题的OJ，这次碰到一道令我颇为头疼的题。
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
题意：给定一只股票N天的股价，一个人最多做出k次交易，而且只有在卖了之后才能买进。问最多能获取的最大利益。
我一开始往DP方向想，但是没什么思路。后来在讨论区看到了一个解法，看明白之后感觉做法挺机智的。
做法：
找出股价的顶点和谷底点，用一个栈保存点对。对于两个点对[v1,p1] [v2,p2],如果v1<v2且p1<p2：如果1. price[v2]<price[v1],那么更优的取法就是分别取price[p2]-price[v2]和price[p1]-price[v1]；
如果2. price[v1]<price[v2],则有两种取法，第一种是取price[p2]-price[v1](等于只做一次交易）,另外一种是price[p2]-price[v2]+price[p1]-price[v1]=(price[p2]-price[v1])+(price[p1]-price[v2])（分开两次做交易）
注意，栈里面的点对不会出现price[p1]<price[v2]的情况的（这个结合代码的具体操作可以保证的）
最后，用优先队列取出前K大的区间，是可以保证不会重复区间的。
代码如下：
//源代码地址：<a target=_blank href="https://leetcode.com/discuss/26745/c-solution-with-o-n-klgn-time-using-max-heap-and-stack">https://leetcode.com/discuss/26745/c-solution-with-o-n-klgn-time-using-max-heap-and-stack</a>
class Solution {//leetcode只需写一个类就行了
public:
int maxProfit(int k, vector<int> &prices) {
int n = (int)prices.size(), ret = 0, v, p = 0;
priority_queue<int> profits;
stack<pair<int, int> > vp_pairs;
while (p < n) {
// find next valley/peak pair
for (v = p; v < n - 1 && prices[v] >= prices[v+1]; v++);
for (p = v + 1; p < n && prices[p] >= prices[p-1]; p++);
// save profit of 1 transaction at last v/p pair, if current v is lower than last v
while (!vp_pairs.empty() && prices[v] < prices[vp_pairs.top().first]) {
profits.push(prices[vp_pairs.top().second-1] - prices[vp_pairs.top().first]);
vp_pairs.pop();
}
// save profit difference between 1 transaction (last v and current p) and 2 transactions (last v/p + current v/p),
// if current v is higher than last v and current p is higher than last p
while (!vp_pairs.empty() && prices[p-1] >= prices[vp_pairs.top().second-1]) {
profits.push(prices[vp_pairs.top().second-1] - prices[v]);
v = vp_pairs.top().first;
vp_pairs.pop();
}
vp_pairs.push(pair<int, int>(v, p));
}
// save profits of the rest v/p pairs
while (!vp_pairs.empty()) {
profits.push(prices[vp_pairs.top().second-1] - prices[vp_pairs.top().first]);
vp_pairs.pop();
}
// sum up first k highest profits
for (int i = 0; i < k && !profits.empty(); i++) {
ret += profits.top();
profits.pop();
}
return ret;
}
};