121. 买卖股票的最佳时机

Posted on | In
Words count in article: 730 | Reading time ≈ 3

题目

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

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

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

示例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
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^4

解法：

解法一：

暴力计算

Java

1
2
3
4
5
6
7
8
9
10
11
public int maxProfit(int[] prices) {
		int max = 0;
		for (int i = 0;i < prices.length;i++) {
			for (int j = i + 1;j < prices.length;j++) {
				if (prices[j] - prices[i] > max) {
					max = prices[j] - prices[i];
				}
			}
		}
		return max;
    }

解法二：

我们可以把数组按照递增区间最小值分为几个部分。

比如针对数组[7,1,5,3,6,4]就可以分为[7]和[1,5,3,6,4]这两个部分，然后在这两个部分中分别求最大的差值。

为什么这么分呢？

获取最大利益，都是想在最低点买入，最高点卖出，那么是不是可以这么考虑，只要某段区间内，最小值没有变化的话，就找到这个区间里面的最大值，两者相减，获得区间最大值，最后和其他区间的最大值比较，取最大的就行了呢？

而数组[7,1,5,3,6,4]，第一个最小值就是7，最小值min初始化为Integer.MAX_VALUE。第二个就是1.因此分为[7]和[1,5,3,6,4]两部分。

而数组[2,5,1,3]就可以分为[2,5]和[1,3]两个部分，因为最小值从2变为了1.

Java

1
2
3
4
5
6
7
8
9
10
11
public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice)
                minprice = prices[i];
            else if (prices[i] - minprice > maxprofit)
                maxprofit = prices[i] - minprice;
        }
        return maxprofit;
    }

解法三：

最大子数组和

股票从买入的那天起，到卖出的那天，所收获的利益就是p[i]-p[i-1] + p[i-1]-p[i-2] + … + p[2] - p[1]。

那么这个问题就可以转化为求最大子数组和的问题。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int maxProfit(int[] prices) {
		int len = prices.length;
		if (len <= 1) {
			return 0;
		}
		int res = 0, currsum = 0;
		for (int i = 1; i < len; i++) {
			if (currsum <= 0) {
				currsum = prices[i] - prices[i - 1];
			} else {
				currsum += prices[i] - prices[i - 1];
			}

			if (currsum > res) {
				res = currsum;
			}
		}
		return res;
	}
0%