描述

假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1. 你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
2. 如果不能获取到任何利润，请返回0
3. 假设买入卖出均无手续费

示例：

1. 输入：[8,9,2,5,4,7,1]
2. 输出：5，买入2，卖出7

思路1：暴力破解，两两组合

时间复杂度O(n^n)，超时

public class Solution {
    public int maxProfit (int[] prices) {
        int ret = 0;
        for(int i = 0; i < prices.length - 1; i++) {
            //卖出在买入之后
            for(int j = i + 1; j < prices.length; j++) {
                ret = Math.max(ret, prices[j] - prices[i]);
            }
        }
        return ret;
    }
}

思路2：双指针一次遍历

1. i表示买入日期，j表示卖出日期，ret记录最大收益
2. prices[j] > prices[i]时，表示上涨，否则表示下跌
3. 上涨时不能买入，i不变，j往后移
4. 下跌时如果比买入价格低，更新买入价格。
5. j继续往后移，查找是否还有上涨期

public class Solution {
    public int maxProfit (int[] prices) {
        int i = 0;
        int j = 1;
        int ret = 0;
        while(j < prices.length) {
            if(prices[j] <= prices[i]) {
                i = j;
            } else if(prices[j] > prices[i]) {
                ret = Math.max(ret, prices[j] - prices[i]);
            }
            j++;
        }
        return ret;
    }
}

思路3：记录最小值一次遍历

记录最小买入价格和最大收益。[5,99,2,5,4,7,1]

类似思路2，思路2是通过i记录最低买入价格日期

public class Solution {
    public int maxProfit (int[] prices) {
        int min = Integer.MAX_VALUE;
        int ret = 0;
        for(int price : prices) {
            ret = Math.max(ret, price - min);
            min = Math.min(price, min);
        }
        return ret;
    }
}