LeetCode_132_BestTimeToBuyAndSellStock


1. question: 买卖股票的最佳时机(简单)

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

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

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

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock

示例 1:

1
2
3
4
输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

示例 2:

1
2
3
输入:prices = [7,6,4,3,1]
输出:0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0。

提示:

1
2
1 <= prices.length <= 105
0 <= prices[i] <= 104

2. answers

这道题和以前的做的买卖股票II类似。只不过本题要求只能买卖一次,但是思路,以贪心的方式来做的话,还是一样的。

注意,单天买入卖出相当于连续多天持有。因此,计算单天的收益,累加收益,每次取最大值。

如果收益结果为负数,说明累加到现在,收益为负数了,显然应该重新计算收益,即清零。再次累加,取最大值。

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class Solution_0132 {

public int maxProfit(int[] prices) {

if(prices.length <= 1) return 0;

int sums = 0;
int maxValue = 0;

// 计算相邻天的利润差
int[] diff = new int[prices.length - 1];
for (int i = 1; i < prices.length; i++) {
diff[i-1] = prices[i] - prices[i-1];
}

// 遍历利润差,注意,因为只能买卖一次,所以当利润出现了负值,说明当前此次交易是不值当的。下次再进行交易
// 注意,时刻比较最大值利润。
for (int value : diff) {

sums += value;
if (sums >= 0) maxValue = Math.max(maxValue, sums);
else sums = 0;
}

return maxValue;
}

public static void main(String[] args) {
System.out.println();

// int[] prices = {7, 1, 5, 3, 6, 4};
int[] prices = {7, 6, 4, 3, 1};

Solution_0132 s = new Solution_0132();

System.out.println(s.maxProfit(prices));
}
}

参考题解,其实贪心还有另一种方式。既然收益最大,显然买入的时候是左侧最小的,卖出的时候是右侧最大的即可。

因此,可遍历数组,每次取最小值,并计算收益(取最大值)。【因为后面的可能比当前的大,所以此时最小值就不变】,计算收益,显然是当前值卖出,【即现在卖出,时刻取收益最大值】。

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution_0132_03 {

public int maxProfit(int[] prices) {

int maxValue = 0;
int low = Integer.MAX_VALUE;

for (int i = 0; i < prices.length; i++) {

low = Math.min(low, prices[i]);
maxValue = Math.max(maxValue, prices[i] - low);
}

return maxValue;
}

public static void main(String[] args) {

System.out.println();

Solution_0132_03 s = new Solution_0132_03();

int[] prices = {7, 1, 5, 3, 6, 4};
// int[] prices = {7, 6, 4, 3, 1};

System.out.println(s.maxProfit(prices));
}
}

那么动态规划该怎么做呢?

1
2
3
4
5
* 参考题解,动态规划:前i天的最大收益 = max{前i-1天的最大收益,第i天的价格-前i-1天中的最小价格}
* 其实本题是找最大值。那么既然遍历到了当天,那么就需要计算当天卖出的收益【怎么知道当天的最大收益呢?只需要找到前面的最低价格即可】。
* 既然有前到后遍历到这,所以肯定能找到最小值。即本天卖出的最大收益可计算到。
*
* 但是前面卖出也有最大值,因此,需要比较取最大值。其实和02解法是一样的思路。

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Solution_0132_04 {

public int maxProfit(int[] prices) {

int min = 0;

int[] dp = new int[prices.length];

dp[0] = Integer.MIN_VALUE;

for (int i = 1; i < prices.length; i++) {

// 保留最小price下标
if(prices[i] < prices[min]) min = i;

// 计算当前price下的最大值。
dp[i] = Math.max(dp[i-1], prices[i] - prices[min]);
}

return Math.max(0, dp[prices.length - 1]);
}

public static void main(String[] args) {
System.out.println();

Solution_0132_04 s = new Solution_0132_04();

// int[] prices = {7,1,5,3,6,4};
int[] prices = {7,6,4,3,1};

System.out.println(s.maxProfit(prices));
}
}

以二维数组,动态规划做一下。每一天的状态只有两个:持有股票、不持有股票。可定义数组dp[i][0]表示第i天持有股票时的最大利润,dp[i][1]表示第i天不持有股票的最大利润。

  1. dp[i][0]只能由前一天持有股票;或者今天买入,即dp[i][0]=max(dp[i-1][0], -prices[i])。不能由前一天不持有股票,今天买入股票得到,因为只能交易一次,显然,今天买入,可能会是第二次交易。
  2. dp[i][1]可由前一天持有股票,今天卖出;或者前一天不持有股票,二者取最大值得到。即dp[i][1]=max(dp[i-1][1], dp[i-1][0] + prices[i])

初始化,第0天dp[0][0] = -prices[0]; dp[0][1] = 0

代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution_0132_06 {

public int maxProfit(int[] prices) {

// 初始化
int[][] dp = new int[prices.length][2];
dp[0][0] = -prices[0];
dp[0][1] = 0;

for (int i = 1; i < prices.length; i++) {

dp[i][0] = Math.max(dp[i-1][0], -prices[i]);

dp[i][1] = Math.max(dp[i-1][1], dp[i][0] + prices[i]);
}

return dp[dp.length - 1][1];
}

public static void main(String[] args) {
System.out.println();

int[] prices = {7,1,5,3,6,4};
// int[] prices = {7,6,4,3,1};

Solution_0132_06 s = new Solution_0132_06();

System.out.println(s.maxProfit(prices));
}
}

3. 备注

参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)代码随想录 (programmercarl.com)


文章作者: 浮云
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 浮云 !
  目录