Leetcode-Array-121.买卖股票的最佳时机

发表于 更新于 分类于 ， 阅读次数： 本文字数： 353 阅读时长 ≈ 1 分钟

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/?envType=study-plan-v2&envId=top-interview-150

思路

  1. 暴力解法，时间复杂度
  2. 遍历，假设在当天卖出（同时假设在当天之前的历史最低点买入，这个很好实现，遍历时存下来即可），找到利益最大的即可。时间复杂度 ，上述解法空间复杂度都是 。

代码

代码很简单，就不需要伪代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxProfit(int[] prices) {
        // 思路上应该是比较明确的，每次假设以前购买的，并在当前时间点卖出
        // 那我们需要知道 如果在当前时间点卖出，对应以前什么时候收购能最大化利益
        // 考虑遍历一次数组，遍历过程中，记录到当前之前的最小值。
        int minprice=prices[0];
        int maxprofit=0;
        for(int i=1;i<prices.length;i++){
            if(prices[i]<minprice)minprice=prices[i];
            else if(prices[i]-minprice>maxprofit)maxprofit=prices[i]-minprice;
        }
        return maxprofit;
    }
}

但是我提交之后，发现竟然还有比我快得多的？？太怪了，赶紧去看。发现人家用了 Math 类实现大小比较与赋值，快得多，赶紧学习一下。

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