leetcode 121.买卖股票的最佳时机

声明：以下仅代表个人想法，非官方答案或最优题解！

题目：

给定一个数组 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。

下面谈谈本人的心路历程：

上来就做。心想，凭w暴力小子的身份，这点问题还是没问题的。第一遍题解如下：

class Solution {public int maxProfit(int[] prices) {int res = 0;// 初始化赋值int temp = 0;// 代表最大利润// 初始化赋值for (int i = 0; i < prices.length; i++) {// i代表被假设的最低价格for (int j = i; j < prices.length; j++) {// j代表被假设的最高价格if (prices[j] > prices[i]) {temp = prices[j] - prices[i];// 更新最大利润if (temp > res) {res = temp;// 更新最大利润}}}}return res;}
}

直接运行，ok没问题。然后提交。。。结果系统判定超时了。。。

也难怪，for了两次，O(n^2)时间复杂度，确实有超时的风险。

然后就是优化了，这一部分思考了很久，先把代码贴出来：

class Solution {public int maxProfit(int[] prices) {int minPrice = Integer.MAX_VALUE;// 初始化赋值int maxProfit = 0;// 初始化赋值for (int i : prices) {if (i < minPrice) {minPrice = i;// 更新最低价格} else {if (i - minPrice > maxProfit) {maxProfit = i - minPrice;// 更新最大利润}}}return maxProfit;}
}

简单说说思路：

最初的实现有两个嵌套的循环，每个循环都会遍历数组。那么可不可以通过“一次遍历”或“贪心算法”的方法去实现呢？

当然是可以的

在股票买卖问题中，最重要的的策略就是“低买高卖”。

因此，我们可以在遍历数组的同时，保持追踪最低价格和到目前为止的最大利润。当发现一个更高的价格时，便可以计算当前价格与最低价格之间的差值，并更新最大利润。如果当前价格比最低价格还低，那么就更新最低价格。

最后，这个算法的时间复杂度是 O(n)，因为它只遍历了一次数组。

至此，这个问题正式结束。

如果你有问题，或者意见及建议，欢迎评论沟通！