【LeetCode】121. 买卖股票的最佳时机

121. 买卖股票的最佳时机

区间内，差值最大，注意并不是最低值和最大值差值就是最大，例如，3，7，1，3，4。差值最大是7-3

解法一: 暴力计算

遍历所有可能性，记录最大值

空间复杂度：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;
}

解法二

股票低买高卖，

假设第一天买进，后面天数买进/卖出

1. 假设买进，价格更低，假设买进min更新当前最少值
2. 假设卖出
   1. 当前卖出利润更大，更新最大利润（此时最大利润当前价格 - 之前价格最低点）
   2. 当前卖出利润更新，则不更新

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;
}