Leetcode 121 买卖股票的最佳时机(Best Time to Buy and Sell Stock) 题解分析

题目介绍

You are given an array prices where prices[i] is the price of a given stock on the i^th day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

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

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

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

简单分析

其实这个跟二叉树的最长路径和有点类似，需要找到整体的最大收益，但是在迭代过程中需要一个当前的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

int maxSofar = 0;
public int maxProfit(int[] prices) {
    if (prices.length <= 1) {
        return 0;
    }
    int maxIn = prices[0];
    int maxOut = prices[0];
    for (int i = 1; i < prices.length; i++) {
        if (maxIn > prices[i]) {
            // 当循环当前值小于之前的买入值时就当成买入值，同时卖出也要更新
            maxIn = prices[i];
            maxOut = prices[i];
        }
        if (prices[i] > maxOut) {
            // 表示一个可卖出点，即比买入值高时
            maxOut = prices[i];
            // 需要设置一个历史值
            maxSofar = Math.max(maxSofar, maxOut - maxIn);
        }
    }
    return maxSofar;
}

总结下

一开始看到 easy 就觉得是很简单，就没有 maxSofar ，但是一提交就出现问题了
对于[2, 4, 1]这种就会变成 0，所以还是需要一个历史值来存放历史最大值，这题有点动态规划的意思