8000 added 106. Best Time to Buy and Sell Stock III · skycache/LeetCode-1@66ce799 · GitHub
[go: up one dir, main page]
Skip to content

Commit 66ce799

Browse files
pezypezy
committed
added 106. Best Time to Buy and Sell Stock III
1 parent 58fb58b commit 66ce799

File tree

3 files changed

+74
-0
lines changed

3 files changed

+74
-0
lines changed

‎106. Best Time to Buy and Sell Stock III/README.md

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
这个问题都出到 III 了，真是无穷无尽啊。参考 [Best Time to Buy and Sell Stock II](../005. Best Time to Buy and Sell Stock II) 与 [Best Time to Buy and Sell Stock](../039. Best Time to Buy and Sell Stock).
2+
3+
这道题从 I 里要求的仅有一次交易，转变为最多可以进行两次交易。那么很自然地，我们还是从一次交易的思路着手。
4+
5+
6 1 3 2 4 7 6 10 15
6+
low: 6 1 1 1 1 1 1 1 1
7+
ret: 0 0 2 2 3 6 6 9 14
8+
^
9+
查看一下 I 中的思路，我们运用了两个变量来完成此事，low 时刻记录最低股价，ret 则不断刷新差价，前者求 min, 后 8000 求 max. 想在反思这种解法，实际上是非常朴素的 DP, 也是一种积累思想的体现。
10+
11+
如果再给我们一次机会，再来一次交易呢？就看上述例子，我们一眼就瞧出了两次交易转手的地方：
12+
13+
6 1 3 2 4 7 6 10 15
14+
low: 6 1 1 1 1 1 1 1 1
15+
ret: 0 0 2 2 3 6 6 9 14
16+
^ ^
17+
6+9 = 15 ---> ret
18+
19+
如果在 7 的时候卖，6 的时候买，那么竟然可以得到 15 的差价。反思一下，我们人脑是如何判别出这个点的。显然，我们可以发现，在 1~15 这个序列里，出现下降趋势的地方仅有两处：3->2, 7->6, 前者我们最终获得的差价也是 15(2+13)。而想要获得最大的差价，需这种下降的地方，下降的更多才是。这里 3-2 == 7-6 == 1. 所以第二次交易至多也只能增加 1.
20+
21+
在 I 里，我们采用了 low + ret 来捕获上升趋势时的变化。而根据上述分析，我们显然还对下降趋势的地方感兴趣。但这个下降有个条件，即一定要是在**总的上升趋势中的小下降**。那么从头开始捕获就不太合理，从尾部开始，或许可以。相似的，我们采用 high + ret 来计算。
22+
23+
6 1 3 2 4 7 6 10 15
24+
ret: 0 0 2 2 3 6 6 9 14
25+
15 15 15 15 15 15 15 15 15 :high
26+
15 15 15 15 15 15 15 14 14 :new_ret
27+
28+
`high` 与 `low` 一样，始终记录最高股价，new_ret 则不断刷新差价。此时的 `new_ret == ret + high - today`. 显然，这一次两者都是求 max 了。
29+
30+
还可以发现的是，上一次迭代每一次 ret 都是对我们这一次的逆向迭代有用的，所以我们最终还是需要 O(n) 的缓存空间。
31+
32+
总结一下，两次迭代，用 vector 记录历史差价。最终得到的 ret 即为所求。AC.

‎106. Best Time to Buy and Sell Stock III/TEST.cc

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
#define CATCH_CONFIG_MAIN
2+
#include "../Catch/single_include/catch.hpp"
3+
#include "solution.h"
4+
using std::vector;
5+
6+
TEST_CASE("First Missing Positive", "[firstMissingPositive]")
7+
{
8+
Solution s;
9+
SECTION( "example" )
10+
{
11+
vector<int> vec{6,1,3,2,4,7,6,10,15};
12+
REQUIRE( s.maxProfit(vec) == 15 );
13+
}
14+
SECTION( "empty" )
15+
{
16+
vector<int> vec;
17+
REQUIRE( s.maxProfit(vec) == 0 );
18+
}
19+
}

‎106. Best Time to Buy and Sell Stock III/solution.h

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
#include <vector>
2+
using std::vector;
3+
#include <algorithm>
4+
using std::min; using std::max;
5+
6+
class Solution {
7+
public:
8+
int maxProfit(vector<int> &prices) {
9+
if (prices.empty()) return 0;
10+
int low = prices.front(), high = prices.back(), ret = 0;
11+
vector<int> history; history.reserve(prices.size());
12+
for (auto today : prices) {
13+
low = min(low, today);
14+
ret = max(ret, today - low);
15+
history.push_back(ret);
16+
}
17+
for (auto today = prices.crbegin(), past = history.crbegin(); today != prices.crend(); ++today, ++past) {
18+
high = max(high, *today);
19+
ret = max(ret, *past + high - *today);
20+
}
21+
return ret;
22+
}
23+
};

0 commit comments

Comments
 (0)
0