题解 | #买卖股票的最好时机(一)#

解题思路 1

1. 存储遇到的最小值并用这个数与后面相减
2. 如果相减收益比目前收益大就选择这个收益

代码实现

这种方法勉强可以达到目的

public class Solution {
    public int maxProfit (int[] prices) {
        // write code here
        int min = prices[0];
        int max = 0;
        for(int i = 1; i<prices.length;i++){
            if(prices[i]-min<0)min = prices[i];
            if(prices[i]-min>0&&prices[i]-min>max)max = prices[i]-min;
        }
        return max;
    }
}
// 运行时间：222ms	超过3.69% 用Java提交的代码
// 占用内存：22216KB	超过5.31%用Java提交的代码

时间复杂度: $O(n)O(n)$

空间复杂度: $O(1)O(1)$