首页 > 代码库 > Best Time to Buy and Sell Stock II
Best Time to Buy and Sell Stock II
这道题目比上一个稍微复杂点，答题思路是要分析价格的走势，找出每一阶段的波谷和波峰，求出每一阶段的利润，然后累加得出总利润。
需要预读下一个数字，判断价格的走向，如果之前在下降，现在上升了，则得到了波谷，如果之前上升，现在下降了，则得到了波峰，每次得到波峰就要累加一次利润，特别指出的是，有可能直到末尾之一都在上升，所以没法用“转折”法判断波峰，那么就要添加对结尾的判断，如果结尾了并且还是在上升，那么结尾的数字就按照波峰来计算。
第一次通过的代码是这样的：
1 public class Solution { 2 public int maxProfit(int[] prices) { 3 4 if(prices.length==0||prices.length==1){ 5 return 0; 6 } 7 8 int profit = 0; 9 boolean isup = prices[1] > prices[0];10 int down = isup ? prices[0] : 0;// 记录低谷11 12 for (int i = 0; i < prices.length - 1; i++) {13 if (prices[i] < prices[i + 1]) {14 // 在上升15 if (isup || i == prices.length - 2) {16 // 如果这是一个上升过程中的一部分，但此时已经到达末尾，则最后一次计算profit，否则继续17 if (isup == false) {18 down = prices[i];19 }20 if (i == prices.length - 2) {21 profit = profit + prices[i + 1] - down;22 }23 } else {24 // 如果这是一次从下降到上升的转折，则prices[i]是新的低谷，更新down数值，将isup设为true25 down = prices[i];26 isup = true;27 }28 } else {29 // 在下降30 if (isup) {31 // 如果这是上升过程中遇到的下降，则表明这是一个下降拐点，需要计算利润并累加32 profit = profit + prices[i] - down;33 isup = false;34 }35 }36 }37 38 return profit;39 40 }41 }
注意第16行代码那块很乱，经过整理，稍作修改，新的代码减少了4行代码，时间从488ms降低到460ms，得到的新代码如下：
1 public class Solution { 2 public int maxProfit(int[] prices) { 3 if ((prices.length == 0) || (prices.length == 1)) { 4 return 0; 5 } 6 7 int profit = 0; 8 boolean isup = prices[1] > prices[0]; 9 int down = isup ? prices[0] : 0; // 记录低谷10 11 for (int i = 0; i < (prices.length - 1); i++) {12 if (prices[i] < prices[i + 1]) {13 // 在上升14 if (!isup) {15 // 如果这是一次从下降到上升的转折，则prices[i]是新的低谷，更新down数值，将isup设为true16 down = prices[i];17 isup = true;18 }19 20 if (i == (prices.length - 2)) {21 // 如果是到达末尾了，则累加利润22 profit = (profit + prices[i + 1]) - down;23 }24 } else {25 // 在下降26 if (isup) {27 // 如果这是上升过程中遇到的下降，则表明这是一个下降拐点，需要计算利润并累加28 profit = (profit + prices[i]) - down;29 isup = false;30 }31 }32 }33 34 return profit;35 }36 }
Best Time to Buy and Sell Stock II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。