大厂面试真题详解:买卖股票的最佳时机-阿里云开发者社区

开发者社区> 算法编程> 正文

大厂面试真题详解:买卖股票的最佳时机

简介: 大厂面试真题详解:买卖股票的最佳时机

假设有一个数组,它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。

在线评测地址:领扣题库官网

样例1

输入: [3, 2, 3, 1, 2]
输出: 1
说明:你可以在第三天买入,第四天卖出,利润是 2 - 1 = 1

样例2

输入: [1, 2, 3, 4, 5]
输出: 4
说明:你可以在第0天买入,第四天卖出,利润是 5 - 1 = 4

样例3

输入: [5, 4, 3, 2, 1]
输出: 0
说明:你可以不进行任何操作然后也得不到任何利润

算法:贪心

很容易想到的贪心算法。对于每一天的价格,我考虑在那天之前的最低价买入,看看是不是能跟新答案。

  • 我们利用一个单元去保存前缀最小值,或者后缀最大值。以下以前缀最小值 low 为例。
  • 若当前的 prices[i]−low能更新答案,则更新
  • low=min(prices[i],low) ,继续跟新最小值即可。

复杂度分析

  • 时间复杂度O(n)

    • 扫描整个数组即可
  • 空间复杂度O(1)

    • 常数空间
      代码
public class Solution {

    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */

    public int maxProfit(int[] prices) {
        // write your code here

        if (prices == null || prices.length == 0) {
            return 0;
        }
        int minPrice = Integer.MAX_VALUE;  //just remember the smallest price
        int maximumProfit = 0;

        for (int i : prices) {
            minPrice = i < minPrice ? i : minPrice;
            maximumProfit = (i - minPrice) > maximumProfit ? i - minPrice : maximumProfit;

        }
        return maximumProfit;
    }
}

更多题解参考:九章官网solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接