买卖股票的最佳时机

给定一个数组 prices 它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润返回 0 。例子输入[7,1,5,3,6,4]输出5解释在第 2 天股票价格 1的时候买入在第 5 天股票价格 6的时候卖出最大利润 6-1 5 。注意利润不能是 7-1 6, 因为卖出价格需要大于买入价格同时你不能在买入前卖出股票。解法一: 暴力计算遍历所有可能性记录最大值空间复杂度O(n)时间复杂度O(n^2)显然这个时间复杂度是不可接受public int maxProfit(int[] prices) { if (prices null || prices.length 1) return 0; int n prices.length; int max 0; for (int i 0; i n; i) { for (int k i 1; k n; k) { int diff prices[k] - prices[i]; if (diff 0 diff max) max diff; } } return max; }解法二股票低买高卖假设第一天买进后面天数买进/卖出假设买进价格更低假设买进min更新当前最少值假设卖出当前卖出利润更大更新最大利润此时最大利润当前价格 - 之前价格最低点当前卖出利润更新则不更新public int maxProfit(int[] prices) { if (prices null || prices.length 1) return 0; int min prices[0], max 0; for (int i 1; i prices.length; i) { if (prices[i] min) { min prices[i]; } else if (prices[i] - min max) { max prices[i] - min; } } return max; }