@2020-11-05
最开始看到这个题目的时候，误以为是要根据现有数据来计算趋势，并判断另一组数据中要买入哪些。
后来发现，其实该问题要的是利润最大化，于是有了几个思路。
1. 思路一
类似于股票中的“蜡烛图”，红色为涨，绿色为跌，利润最大化=所有红色蜡烛的合计。
这种简化的方法，不需要找出所有的“峰值”、“谷值”、“顺序”。
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
int tempProfit = prices[i] - prices[i-1];
if(tempProfit > 0){
maxProfit = tempProfit + maxProfit;
}
}
return maxProfit;
}
}
|
- 时间复杂度：O(n)，仅遍历一次
- 空间复杂度：O(1)，需要常量的空间
2. 思路二
其实这个思路是 “思路一”的源头。即要获得最大利润，就要知道所有的谷及其后紧邻的峰，实现“低买高卖”。
$$
TotalProfits = \sum_{i}(Height(Peak_i) - Height(Valley_i))
$$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int maxProfit(int[] prices) {
int i = 0;
int valley = prices[0];
int peak = prices[0];
int maxprofit = 0;
while (i < prices.length - 1) {
while (i < prices.length - 1 && prices[i] >= prices[i + 1])
i++;
valley = prices[i];
while (i < prices.length - 1 && prices[i] <= prices[i + 1])
i++;
peak = prices[i];
maxprofit += peak - valley;
}
return maxprofit;
}
}
|
- 时间复杂度：O(n)。遍历一次。
- 空间复杂度：O(1)。需要常量的空间。
3. 思路三
关于这一条，其实是从 LeetCode 的解题思路中看到的，要计算所有可能的交易组合。
太麻烦就没有继续看了。