算法:买卖股票的最佳时机

算法 大约 974 字

题目

给定一个数组prices,它的第i个元素prices[i]表示一支给定股票第i天的价格。

你只能选择某一买入这只股票,并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回0

实现

方法一

  1. 记录【今天之前买入的最小值】
  2. 计算【今天之前最小值买入,今天卖出的获利】,也即【今天卖出的最大获利】
  3. 比较【每天的最大获利】,取最大值即可
public static int maxProfit(int[] prices) {
    int min = prices[0];
    int maxProfit = 0;

    for (int i = 1; i < prices.length; i++) {
        int profit = prices[i] - min;
        maxProfit = Math.max(profit, maxProfit);
        min = Math.min(min, prices[i]);
    }
    return maxProfit;
}

方法二

暴力比较

public static int maxProfit(int[] prices) {
    int maxProfit = 0;
    for (int i = 0; i < prices.length - 1; i++) {
        for (int j = i + 1; j < prices.length; j++) {
            if (prices[j] > prices[i]) {
                maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
            }
        }
    }
    return maxProfit;
}

超出时间限制。- -!

LeetCode 原题地址

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/comments

阅读 201 · 发布于 2021-02-25

————        END        ————

扫描下方二维码关注公众号和小程序↓↓↓

扫描二维码关注我
昵称:
随便看看 换一批