leetcode 121.Best Time to Buy and Sell Stock

2017-08-03

题意

给定一个数组来标识股票的价格，找到最能赚钱的买卖点，返回赚到的钱

我的思路

比较容易想到穷举遍历法

我的代码

穷举遍历法

public class Solution {
    public int maxProfit(int[] prices) {
        int max = 0;
        for(int i=prices.length-1;i>=0;i--)
            for(int j=i-1;j>=0;j--)
            {
                if((prices[i]-prices[j])>max) max = prices[i]-prices[j];
            }
        return max;
    }
}

这么做是会超时的。

优化代码把效率提升一个级别

1 2	O(n^2) -> O(n)

从左开始找股票的最小值，并且遍历的时候拿去当前值

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length<2) return 0;
        int min = prices[0];
        int result = 0;
        for (int i=1;i<prices.length;i++){
            min = min<prices[i]?min : prices[i];
            result = (prices[i]-min)>result?(prices[i]-min):result;
        }
        return result;
    }
}