买卖股票的最佳时机I 题解

题目详情

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

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

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

示例 1：

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

示例 2：

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

提示：

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

题解

题目重要内容解析：

只能进行一次买卖

首先我们要知道，我们不能先排序再进行最大值见最小值，因为，今天不能买昨天的股票，也就是说，股票具有时效性

其次，既然题目要求的是最大值，所以我们就要尽可能少的在高位抛出，低位卖出，因此在示例一中，我们不能在第一天买入，第二天抛出，尽量避免类似于这样的操作

解法1

所以，我们最开始最容易想到的就是暴力解法，利用双层for循环来求解，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int maxProfit(int[] prices) {
    int max = 0;
    for (int i = 0; i < prices.length; i++) {
        int currPrice = prices[i];
        int temp;
        for (int j = i, pricesLength = prices.length; j < pricesLength; j++) {
            int price = prices[j];
            if (price > currPrice) {
                temp = price - currPrice;
                if (temp > max) {
                    max = temp;
                }
            }
        }
    }
    return max;
}

首先这种解法结果肯定是没有问题的，但是时间复杂度就来到了O(n^2)，我们在leetcode中这样提交是要报超时错误的

image-20231213203504252

当然这也是在数据量特别大的时候才会报超时，所以，我们就要优化一下，如何优化呢？看解法二

解法2

我们首先要思考一下，双层for循环的作用是什么，在我看来，作用是为了和数组中的下一位数进行比较，那么我们可不可以假定数组的第一位是最小的数，然后通过一次遍历来解决问题

1
2
3
4
5
6
7
8
9
10
11
12
public int maxProfit(int[] prices) {
    int minPrice = prices[0];
    int maxProfit = 0;
    for (int price : prices) {
        if (price < minPrice) {
            minPrice = price;
        } else if (price - minPrice > maxProfit) {
            maxProfit = price - minPrice;
        }
    }
    return maxProfit;
}

image-20231213205042573

当然上面的代码还可以再简化一点

1
2
3
4
5
6
7
8
9
public static int maxProfit(int[] prices) {
    int cost = Integer.MAX_VALUE;
    int profit = 0;
    for (int price : prices) {
        cost = Math.min(cost, price);
        profit = Math.max(profit, price - cost);
    }
    return profit;
}

这两种写法结果是一样的，效果也是一样的