122th 买卖股票的最佳时机 II
-
游标思想
定义：index为判断游标，valley表示波谷点，peak表示波峰点。
例如对于数据[7, 1, 5, 3, 6, 4]，第一个波谷-波峰为1-5，第二个波谷波峰为3-6。
显然，1-5的差为4，3-6的查为3，它们的和为7，而1-6的和仅为5。
根据三角形两边之和大于第三边，易知我们只需要统计所有波峰与波谷之差的和即为最大值。
例如对于数据[1, 7, 2, 3, 6, 7, 6, 7]，针对第二个连续波谷-波峰2-3-6-7。
显然，它们之中2-3 3-6 6-7之差的和等于2-7，因此我们需要把游标放在最顶的波峰。
class Solution { public int maxProfit(int[] prices) { if (prices.length == 0 || prices.length == 1) return 0; int ans = 0; int index = 0; int valley = prices[0]; int peak = prices[0]; while (index < prices.length-1) { while (index < prices.length-1 && prices[index] >= prices[index + 1]) index++; valley = prices[index]; while (index < prices.length-1 && prices[index] <= prices[index + 1]) index++; peak = prices[index]; ans += (peak - valley); } return ans; } } -
极简思想
基于上面的思路，我们发现
"例如对于数据[1, 7, 2, 3, 6, 7, 6, 7]，针对第二个连续波谷-波峰2-3-6-7。
显然，它们之中2-3 3-6 6-7之差的和等于2-7，因此我们需要把游标放在最顶的波峰。"
因此我们实际只用综合所有波分-波谷之差的和即可。
class Solution { public int maxProfit(int[] prices) { if (prices.length == 0 || prices.length == 1) return 0; int ans = 0; for(int i = 1; i < prices.length; i++) { if(prices[i-1]<prices[i]) { ans += (prices[i]-prices[i-1]); } } return ans; } }