【LeetCode】121. 买卖股票的最佳时机（剑指 Offer 63）

一、题目

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。

注意：你不能在买入股票前卖出股票。

示例 1:

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

示例 2:

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

二、解决

1、暴力

思路：

取整个数组任意两个数，相减结果取最大。

代码：

class Solution { public int maxProfit(int[] prices) { int profit = 0; for (int i = 0; i < prices.length; i++) { for (int j = i; j >= 0; j--) { profit = Math.max(profit, prices[i]-prices[j]); } } return profit; } }

时间复杂度： $O(n^2)$ 空间复杂度： $O(1)$

2、贪心

思路：

只要比最低点高，则不断累加其高度差，如果比最低点还低，则累加的高度差会小于0，此时把当前最大值置为0。最后返回整个遍历过程的最大高度差。

代码：

class Solution { public int maxProfit(int[] prices) { int maxCur = 0, maxSoFar = 0; for(int i = 1; i < prices.length; i++) { maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]); maxSoFar = Math.max(maxCur, maxSoFar); } return maxSoFar; } }

时间复杂度： $O(n)$ 空间复杂度： $O(1)$

3、当前-最小

思路：

不断遍历元素，在已经遍历的元素中取最小值，然后将当前元素与最小值相减，取整个最大值。

代码：

class Solution { public int maxProfit(int[] prices) { int min = Integer.MAX_VALUE, max = 0; for (int i = 0; i < prices.length; i++) { min = Math.min(min, prices[i]); max = Math.max(max, prices[i] - min); } return max; } }

时间复杂度： $O(n)$ 空间复杂度： $O(1)$

三、参考

1、Kadane’s Algorithm - Since no one has mentioned about this so far 😃 (In case if interviewer twists the input) 2、Java 6 lines, 4 lines, 2 lines solutions 3、Clean Java solution with O(n) time and O(1) space