Nicksxs's Blog

What hurts more, the pain of hard work or the pain of regret?

0%

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 ith 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,所以还是需要一个历史值来存放历史最大值,这题有点动态规划的意思

请我喝杯咖啡