专栏首页程序员的碎碎念LeeCode 每日一题121:股票卖出的最佳时机

LeeCode 每日一题121:股票卖出的最佳时机

开了一个新坑, 今天附带了一个改一条语句提升10倍性能的彩蛋.

题目

动手试试再看解决方法吧

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。 如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入
     在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

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

暴力解决

首先来看看暴力解决这道题的算法,以类似冒泡算法的方式,两层遍历整个数组确定最大利润, 这种方式最蠢, 最容易想到. 在 LeeCode 中, C语言凭借更好的性能还能通过, 而Python就直接超时了.

(想不到这种解法还能超过25%的提交,看来不够暴力)

C语言实现:

int maxProfit(int* prices, int pricesSize) {
    int i, j;
    int maxProfit = 0;

    for(i = 0; i<pricesSize-1; i++){
        for(j=i+1; j<pricesSize; j++){
            if(prices[i]<prices[j] && prices[j]-prices[i]>maxProfit){
                maxProfit = prices[j]-prices[i];
            }
        }
    }

    return maxProfit;
}

Python实现

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        max_profit = 0
        for i in range(len(prices)-1):
            for j in range(i+1, len(prices)):
                if(prices[j]-prices[i] > max_profit):
                    max_profit = prices[j]-prices[i]
        return max_profit

动态规划

查找整个数组的最大利润

转化为查找到当前位置的最大利润, 而到当前的最大利润又可以转化为此前最大利润当前卖出和最小买入股票之差.

有点绕?转化为伪代码试试:

前i天的最大收益 = max{前i-1天的最大收益第i天的卖出价格-前i-1天最小买入价格}

C实现

int maxProfit(int* prices, int pricesSize) {
    if(pricesSize < 0)
        return 0;

    int i, j;
    int maxProfit = 0;
    int minPrice = prices[0];

    for(i = 0; i<pricesSize; i++){
        minPrice = (minPrice>prices[i])?prices[i]:minPrice;
        maxProfit = (maxProfit>prices[i]-minPrice)?maxProfit:prices[i]-minPrice;
    }

    return maxProfit;
}

看到居然才超过43%的用户,我又再检查了一遍, 把三目运算改为普通的 ifelse,然后神奇的事情发生了...

改完超过了99.38%的用户! 耗时瞬间从 48 ms 下降至 4 ms, 一个小小语句提升了10倍性能, 可见三目运算耗能之大.

C语言实现改进版

int maxProfit(int* prices, int pricesSize) {
    if(pricesSize < 0)
        return 0;

    int i, j;
    int maxProfit = 0;
    int minPrice = prices[0];

    for(i = 0; i<pricesSize; i++){
        if (prices[i] - minPrice > maxProfit)
            maxProfit = prices[i] - minPrice;
        if (prices[i] < minPrice)
            minPrice = prices[i];
    }

    return maxProfit;
}

Python 实现

class Solution:
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        max_profit = 0
        if(len(prices)>0): 
            min_price = prices[0]
            for i in range(len(prices)):
                min_price = min(min_price, prices[i])
                max_profit = max(max_profit, prices[i] - min_price)
            return max_profit
        else:
            return max_profit

本文分享自微信公众号 - 程序员的碎碎念(gh_53e607dd4782)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-06

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 每日一题169: 求众数

    给定一个大小为 n 的数组,找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

    benny
  • php实现快速排序算法

    每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在...

    benny
  • php实现归并排序算法

    归并操作(merge),也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。 如 设有数列{6,202,100,301,38,8,1} 初始状态:6,2...

    benny
  • leecode刷题(2)-- 买卖股票的最佳时机

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

    希希里之海
  • CDQ分治小结

    显然我们可以先把所有数都按\(a_i\)排序一遍,这样考虑每个位置\(i\)的时候只需要考虑它前面的贡献即可

    attack
  • java 算法题 - 面试中常见的位操作算法题

    上一篇博客 聊一聊 Android 中巧妙的位操作 中,我们讲解了 java 中常用的位运算及常用应用场景,今天,让我们一起来看一下,面试中常见的位操作的算法题...

    用户2965908
  • 欧拉计划——38全数字的倍数

    连接这些乘积,我们得到一个1至9全数字的数192384576。我们称192384576为192和(1,2,3)的连接乘积。

    lop
  • 微信小程序|两种基本配置

    轮播图能够让我们的微信小程序显得更加美观,微信小程序中总是需要很多点击页面的跳转,那我们运用什么样的代码才能够实现呢?

    算法与编程之美
  • 好消息---Gmail增加免费POP3支持

    Google网页数扩至80亿 增加免费POP3支持 (2004.11.12)   来自:ZDNET    在发布到Google公司blo...

    数据和云01
  • 经典笔试题-C++篇

    答:for 循环中的变量i 的类型不应定义为vector::size_type, 因为该类型为无符号数值类型,故循环条件将恒成立,为死循环,应将其类型定义为有...

    cwl_java

扫码关注云+社区

领取腾讯云代金券