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

121. 买卖业务股票的最佳时机

区间内，差值最大，注意并不是最低值和最大值差值就是最大，比方，3，7，1，3，4。差值最大是7-3
解法一: 暴力盘算

遍历全部大概性，记录最大值
空间复杂度：O(n)
时间复杂度：O(n^2)
显然这个时间复杂度是不可担当

1. public int maxProfit(int[] prices) {
2.     if (prices == null || prices.length <= 1)
3.         return 0;
5.     int n = prices.length;
6.     int max = 0;
7.     for (int i = 0; i < n; i++) {
8.         for (int k = i + 1; k < n; k++) {
9.             int diff = prices[k] - prices[i];
10.             if (diff > 0 && diff > max)
11.                 max = diff;
12.         }
13.     }
14.     return max;
15. }

复制代码

解法二

股票低买高卖，
假设第一天买进，背面天数买进/卖出

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

1. public int maxProfit(int[] prices) {
2.     if (prices == null || prices.length <= 1)
3.         return 0;
5.     int min = prices[0], max = 0;
6.     for (int i = 1; i < prices.length; i++) {
7.         if (prices[i] < min) {
8.             min = prices[i];
9.         } else if (prices[i] - min > max) {
10.             max = prices[i] - min;
11.         }
12.     }
13.     return max;
14. }

复制代码