题目描述

算法1\

class Solution {
    public int maxDiff(int[] nums) {
        //只需要遍历数组一遍，记录历史最低点
        //然后再考虑这么一个问题：如果我是在历史最低点买进的，今天能够卖多少钱
        if(nums.length<2) return 0;
        int max=0;
        int min=nums[0];
        for(int i=1;i<nums.length;i++){
            if(nums[i]<min){
                min=nums[i];
            }else if(max<nums[i]-min){
                max=nums[i]-min;
            }
        }
        return max;

    }
} 

时间复杂度 o(n) 空间复杂度o(1)

算法2

class Solution {
    public int maxDiff(int[] nums) {
        if(nums.length<2) return 0;
        int max=0;
        int curmax=0;//当前交易的最大值
        int price=nums[0];
        for(int i=1;i<nums.length;i++){
            if(nums[i]>price){
                curmax=nums[i]-price;
            }else{
                price=nums[i];
            }
            max=Math.max(max,curmax);
        }
        return max;

    }
}

时间复杂度 o(n) 空间复杂度o(1)