专栏首页渔夫算法-买卖股票的最佳时机 II

算法-买卖股票的最佳时机 II

版权声明: https://blog.csdn.net/li_xunhuan/article/details/89817258

题目:给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。

示例 2:

输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。 因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1] 输出: 0 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

我的代码:
class Solution {
public int maxProfit(int[] prices) {
     if(prices.length==0){
        return 0;
    }
    int minPrice=prices[0];
    int maxPrice=prices[0];
    int income =0;
    for(int i=1;i<prices.length-2;){
        if(prices[i-1]>prices[i]&&prices[i]<prices[i+1]){
             minPrice=prices[i];
            while(prices[i+1]>=prices[i]&&i<prices.length-1){
            i++;    
            }
            
        }
        income+=prices[i]-minPrice;
        
        
    }
 return income;
}
}

上述代码是不正确的,执行实际上会陷入死循环;我对于数组遍历的舒适区是用for循环,但是实际上for语句和while语句都是有各自的适用的地方,而且可以相互转换。不是说遍历一个数组必须要用for语句; 我尝试着找到每个波谷后,在去寻找波谷后面的第一个波峰 但是不知为何程序陷入了死循环;我确信一点:Java中for循环语句中的自加可以放置于放置for(){于此}和C语言类似,不用一定放于()内;但是在一个for语句中采用while语句来控制循环次数变量自增似乎不是一个好主意,实际上想法很简单,却是用了复杂的结构;我们不妨将遍历的for语句改写为while语句:

代码:
for(int i=0;i<a.length-1;i++){
循环体
}
等价于:
int i=0;
while(i<a.length-1){
循环体
i++;
}

所以我们有了一下的代码:

代码:
class Solution {
public static int income(int[] prices) {
     if(prices.length==0){
        return 0;
    }
    int minPrice = prices[0];
    int maxPrice = prices[0];
    int income = 0;
    int i = 0;
    while (i < prices.length - 1) {
        while (i < prices.length - 1 && prices[i] >= prices[i + 1])
            i++;
        minPrice = prices[i];
        while (i < prices.length - 1 && prices[i] <= prices[i + 1])
            i++;
        maxPrice = prices[i];
        income += maxPrice - minPrice;
    }
    return income;
}
}

而且实际上波谷minPrice的判断不必一定去麻烦去使用: prices[i-1]>prices[i]&&prices[i]<prices[i+1]来进行判断,占内存,代码长 实际上高中老师告诉我们,函数递减区间的中断处必定是极小值点; 函数递增区间的中断点必定是极大值点;所以转换为代码就是:

 while (i < prices.length - 1 && prices[i] >= prices[i + 1])
       i++;
       minPrice = prices[i];

这样的实现节省了代码 节约了内存 显得更加漂亮一些

连续的单调增 单调减 如果成立 i++;来进行遍历 这是这个算法的精髓

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 算法:有效括号

    版权声明: ...

    Fisherman渔夫
  • shell、cmd、dos和脚本语言区别和联系

    在windows系统中,“开始-运行-cmd”可以打开“cmd.exe”,进行命令行操作。 操作系统可以分成核心(kernel)和Shell(外壳)两部分,其...

    Fisherman渔夫
  • 算法-股票交易

    版权声明: ...

    Fisherman渔夫
  • LeetCode 121. 买卖股票的最佳时机

    如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。

    freesan44
  • 【leetCode】股票的最大利润day12

    居士
  • 【leetcode刷题】T14-买卖股票的最佳时机 II

    今天分享leetcode第14篇文章,也是leetcode第122题—买卖股票的最佳时机

    木又AI帮
  • 算法模板——计算几何2(二维凸包——Andrew算法)

    实现功能:求出二维平面内一对散点的凸包(详见Codevs 1298) 很神奇的算法——先将各个点按坐标排序,然后像我们所知的那样一路左转,求出半边的凸包,然后反...

    HansBug
  • 1601: [Usaco2008 Oct]灌水

    1601: [Usaco2008 Oct]灌水 Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 1342  S...

    HansBug
  • 微信拍了拍你

    微信已经升级至最新版的朋友,请打开聊天窗口,双击好友的头像,接下来就是见证惊喜的时刻? ? 是的,好友的头像不仅会抖两下,群里还会提示「你拍了拍XX」,被拍...

    腾讯大讲堂
  • Python跳出循环语句continue

    虽然在Python中的for循环与其它语言不大一样,但跳出循环还是与大多数语言一样,可以使用关键字continue跳出本次循环或者break跳出整个for循环。...

    py3study

扫码关注云+社区

领取腾讯云代金券