当前播放: 25 | 面试题:买卖股票的最佳时机
00:00 / 00:00
高清
  • 高清
1.0x
  • 2.0x
  • 1.5x
  • 1.25x
  • 1.0x
  • 0.5x
网页全屏
全屏
00:00
付费课程,可试看
课程目录
第一章:课程综述 (4讲)
01 | 合格程序员的第一步:算法与数据结构
免费
02 | 如何事半功倍地学习算法与数据结构
免费
03 | 如何计算算法的复杂度
免费
04 | 如何通过LeetCode来进行算法题目练习
免费
第二章:理论讲解+面试题实战 (53讲)
05 | 理论讲解:数组&链表
免费
06 | 面试题:反转一个单链表&判断链表是否有环
07 | 理论讲解:堆栈&队列
08 | 面试题:判断括号字符串是否有效
09 | 面试题:用队列实现栈&用栈实现队列
10 | 理论讲解:优先队列
11 | 面试题:返回数据流中的第K大元素
12 | 面试题:返回滑动窗口中的最大值
13 | 理论讲解:哈希表
14 | 面试题:有效的字母异位词
15 | 面试题:两数之和
16 | 面试题:三数之和
17 | 理论讲解:树&二叉树&二叉搜索树
18 | 面试题:验证二叉搜索树
19 | 面试题:二叉树&二叉搜索树的最近公共祖先
20 | 理论讲解:二叉树遍历
21 | 理论讲解:递归&分治
22 | 面试题:Pow(x,n)
23 | 面试题:求众数
24 | 理论讲解:贪心算法
25 | 面试题:买卖股票的最佳时机
26 | 理论讲解:广度优先搜索
27 | 理论讲解:深度优先搜索
28 | 面试题:二叉树层次遍历
29 | 面试题:二叉树的最大和最小深度
30 | 面试题:生成有效括号组合
31 | 理论讲解:剪枝
32 | 面试题:N皇后问题
33 | 面试题:数独问题
34 | 理论讲解:二分查找
35 | 面试题:实现一个求解平方根的函数
36 | 理论讲解:字典树
37 | 面试题:实现一个字典树
38 | 面试题:二维网格中的单词搜索问题
39 | 理论讲解:位运算
40 | 面试题:统计位1的个数
41 | 面试题:2的幂次方问题&比特位计数问题
42 | 面试题:N皇后问题的另一种解法
43 | 理论理解:动态规划(上)
44 | 理论理解:动态规划(下)
45 | 面试题:爬楼梯
46 | 面试题:三角形的最小路径和
47 | 面试题:乘积最大子序列
48 | 面试题:股票买卖系列
49 | 面试题:最长上升子序列
50 | 面试题:零钱兑换
51 | 面试题:编辑距离
52 | 理论讲解:并查集
53 | 面试题:岛屿的个数&朋友圈(上)
54 | 面试题:岛屿的个数&朋友圈(下)
55 | 理论讲解: LRU Cache
56 | 面试题:设计和实现一个LRU Cache缓存机制
57 | 理论讲解:布隆过滤器
第三章:课程总结 (5讲)
58 | 课程重点回顾
59 | FAQ答疑&面试中切题四件套
60 | 回到起点:斐波拉契数列
61 | 白板实战番外篇:斐波拉契数列
62 | 结课测试&最后的一些经验分享
25 | 面试题:买卖股票的最佳时机

25 | 面试题:买卖股票的最佳时机

覃超
Sophon Tech创始人,前Facebook工程师,卡内基梅隆大学计算机硕士
全集23612
新人首单 ¥29.9 原价 ¥129
13
登录 后留言

精选留言(20)

  • 石头
    纪念一下我的第一次 “faster then 100%” (裸写的)
    “Runtime: 1 ms, faster than 100.00% of Java online submissions for Best Time to Buy and Sell Stock II.”
         public int maxProfit(int[] prices) {
            int profit = 0;
            for (int i = 0; i < prices.length - 1; i++) {
                if (prices[i] < prices[i + 1]) {
                    profit += prices[i + 1 ] - prices[i];
                }
            }
            return profit;
        }
    2019-01-15
    7
  • Enhao
    DFS里每天有三种情况吧:
    1. 买
    2. 卖
    3. 不动
    2019-09-17
    2
  • mickey
    class Solution {
        public int maxProfit(int[] prices) {
            if (prices == null || prices.length <= 1)
    return 0;

    int value = 0;
    int yestoday = prices[0];
    for (int i = 0; i < prices.length; i++) {
    // 是否卖出?
    int today = prices[i];
    if (i > 0) {
    if (today > yestoday) {
    value += today;
    }
    yestoday = today;
    }

    // 是否买入?
    if (i + 1 < prices.length) {
    int tomm = prices[i + 1];
    if (tomm > today) {
    value -= today;
    }
    }
    }
    return value;
        }
    }
    2020-03-04
    1
  • Derek
    GO语言版本实现:

    func maxProfit(prices []int) int {
    var max int
    for i := 0; i < len(prices)-1; i++ {
    if prices[i+1] > prices[i] {
    max += prices[i+1] - prices[i]
    }
    }
    return max
    }
    2019-02-08
    1
  • fiveone.lwq
    老师深度优先搜索怎么写啊,列出所有的情况
    2018-12-18
    1
  • zhimin
    老师的算法也太牛了, 贪心算法的既简单又好理解。
     function maxProfit($prices) {
            $profit = 0;
            //用贪心算法实现
            for($i=0; $i<count($prices)-1; $i++){
                if($prices[$i] > $prices[$i+1]){
                    continue;
                }else{
                    $profit += $prices[$i+1] - $prices[$i];
                }
            }
            return $profit;
        }
    2020-03-31
  • Jackie Ma
    def maxProfit(self, prices: List[int]) -> int:
            profit = 0
            for i in range(len(prices)):
                if i > 0 and prices[i] > prices[i - 1]:
                    profit += prices[i] - prices[i - 1]
            return profit
    2020-03-22
  • polk
    还在奋斗迭代的方法...每次倒迭代就卡死
    2020-03-07
  • Sochooligan
    能抽象出这个题的人真了不起
    2020-03-03
  • tomlelouch
    class Solution {
      public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
          return 0;
        }
        int profit = 0;
        for (int i = 1; i < prices.length; i++) {
          if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
          }
        }
        return profit;
      }
    }
    2020-01-17
  • Aliliin
    贪心算法 PHP 实现:
    function maxProfit($prices)
        {
            $j = 1;
            $res = 0;
            for ($i = 0; $i < count($prices); $i++) {
                if (!empty($prices[$j]) && $prices[$j] > $prices[$i]) {
                    $res += $prices[$j] - $prices[$i];
                }
                $j++;
            }
            return $res;
        }
    2019-11-09
  • 码农Kevin亮
    请问老师,对于交易k次的泛化版本,我看所有通过的算法都是在买入的状态转移方程中使用k-1,当我尝试换成卖出时才使k-1的话,是无法通过测试用例的。我不太明白其中的原理,而老师在写白板推导时也是在这个细节出了差错,希望老师可以补充说明
    2019-10-09
  • czh
    将问题抽象为层次问题,利用树的遍历来暴力搜,然后在这个版本基础上改进
    2019-09-27
  • Vilochen.
    递归方式:
    public int maxProfit2(int[] prices) {
            return Math.max(maxProfit2(prices, 0, true)
                    , maxProfit2(prices, 0, false));
        }

        public int maxProfit2(int[] prices, int i, boolean buy) {
            if (i >= prices.length - 1) {
                return 0;
            }
            if (buy) {
                int sum = 0;
                if (prices[i] < prices[i + 1]) {
                    sum = prices[i + 1] - prices[i];
                }
                return Math.max(maxProfit2(prices, i + 1, true)
                        , maxProfit2(prices, i + 1, false)) + sum;
            } else {
                return Math.max(maxProfit2(prices, i + 1, true)
                        , maxProfit2(prices, i + 1, false));
            }
        }
    2019-05-27
  • Salad
    老师DFS这个方法该怎么实现呀
    2019-05-03
  • Allen_
    有个问题, 为什么DFS的时间复杂度是2^n? 如果遍历一遍,每一天的价格和后面的每一天计算利润的话,不应该是1+2+。。。+n-1吗?应该是N^2?
    2019-02-25
  • kilien
    def maxProfit(self, prices: 'List[int]') -> 'int':
            profit = 0
            for i, x in enumerate(prices):
                if i == len(prices) - 1: return profit
                if x < prices[i+1]:
                    profit += prices[i+1] - x
            return profit

    作者回复: 帅!

    2019-02-22
  • Aries
    def maxProfit(self, prices):
            pro = 0
            for i in range(1,len(prices)):
                a = prices[i-1] - prices[i]
                if a < 0:
                    pro -= a
            return pro
    这是动规还是贪心呢
    2018-12-26
  • 吴小智
    老师能否讲一下,为什么在这种情况下用贪心算法,得到的确实是最大的收益?能否结合子问题的方式来讲一下。
    2018-12-24
  • 王磊
    搜索算法每一天的操作是买/卖,和不操作。是买是卖取决于当前的持仓状态。
    2018-10-27
收起评论
看过的人还看
数据结构与算法之美

王争  前Google工程师

80讲 | 87516 人已学习

新人首单 ¥29.9 原价 ¥129
趣谈网络协议

刘超  网易研究院云计算技术部首席架构师

51讲 | 45344 人已学习

新人首单 ¥19.9 原价 ¥99
左耳听风

陈皓  网名“左耳朵耗子”,资深技术专家,骨灰级程序员

109讲 | 45998 人已学习

新人首单 ¥69.9 原价 ¥299
Java核心技术面试精讲

杨晓峰  前Oracle首席工程师

44讲 | 46893 人已学习

新人首单 ¥19.9 原价 ¥99