[Leetcode] Best Time to Buy and Sell Stock 买卖股票的最佳

摘要：双指针法复杂度时间空间思路根据买卖股票的特性，我们必须先低价买，再高价卖，这个找最大收益的过程实际上是找到目前为之的最低价。我们可以利用这个之前计算的结果降低时间复杂度不过代价是额外空间，所以需要把到的最大收益存在数组中。

Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

时间 O(N) 空间 O(1)

根据买卖股票的特性，我们必须先低价买，再高价卖，这个找最大收益的过程实际上是找到目前为之的最低价。在遍历价格数组时，根据这个动态更新的最低价和当前的价格可以算出当前卖股票最大能赚多少钱。

public class Solution {
    public int maxProfit(int[] prices) {
        int min = Integer.MAX_VALUE, res = 0;
        for(int i = 0 ; i < prices.length; i++){
            if(prices[i]res) res = prices[i] - min;
        }
        return res;
    }
}

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

时间 O(N) 空间 O(1)

既然能买卖任意次，那最大收益的方法就是尽可能多的低入高抛。只要明天比今天价格高，就应该今天买入明天再卖出。

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

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

时间 O(N) 空间 O(N)

最简单的方法就是对每一个时间点，将其所有两边的数组都执行一次Best Time to Buy and Sell Stock I的解法，但这会带来O(N^2)的时间复杂度。实际上当计算prices[0]到prices[i]的最大收益时，我们已经计算过prices[0]到prices[i-1]的最大收益了，prices[0]到prices[i]的最大收益应该是当前卖出能获得的最大收益和prices[0]到prices[i-1]的最大收益中，二者较大的那个。我们可以利用这个之前计算的结果降低时间复杂度（不过代价是额外空间），所以需要把prices[0]到prices[i]的最大收益存在left[i]数组中。具体解法和I是一样的，也是维护一个前半段最小值。

分别得出以i点为分割点，左半段最大收益的数组left，和右半段最大收益的数组right后，我们就可以遍历一遍这两个数组，找出最大的left+right组合。实际上，该解法就是将I的解法双向各执行一遍并记录结果。

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length == 0) return 0;
        int[] left = new int[prices.length];
        int[] right = new int[prices.length];
        int leftMin = prices[0];
        int rightMax = prices[prices.length-1];
        int sum = 0;
        //计算左半段最大收益
        for(int i = 1 ; i < prices.length; i++){
            leftMin = Math.min(prices[i], leftMin);
            left[i] = Math.max(prices[i] - leftMin, left[i-1]);
        }
        //计算右半段最大收益
        for(int i = prices.length - 2 ; i >= 0; i--){
            rightMax = Math.max(prices[i], rightMax);
            right[i] = Math.max(rightMax - prices[i], right[i+1]);
        }
        //找出两次交易最大收益组合
        for(int i = 0 ; i < prices.length; i++){
            if((left[i]+right[i])>sum) sum = left[i]+right[i];
        }
        return sum;
    }
}

时间 O(N) 空间 O(1)

其实我们并不需要知道每个时间点买卖第一第二笔股票收益的全部信息，我们只要知道前一个时间点买卖第一第二笔股票的最大收益信息，就可以直到当前最大的收益信息了，这样可以为我们省去额外空间。这里我们遍历prices数组的时候，维护四个变量:release2是在该价格点卖出第二笔股票后手里剩的钱，等于上一轮买入第二笔股票后手里剩的钱加上卖出当前股票价格的钱，或者上一轮卖出第二笔股票后手里剩的钱两者中较大的。hold2是在该价格点买入第二笔股票后手里剩的钱，等于上一轮卖出第一笔股票后手里剩的钱减去买入当前股票价格的钱，或者上一轮买入第二笔股票后手里剩的钱两者中较大的。release1是在该价格点卖出第一笔股票后手里剩的钱，等于上一轮买入第一笔股票后手里剩的钱加上卖出当前股票价格的钱，或者上一轮卖出第一笔股票后手里剩的钱两者中较大的。hold1是在该价格点买入第一笔股票后手里剩的钱，等于初始资金减去买入当前股票价格的钱或者初始资金（不买）中较大的。这里计算顺序按照release2 -> hold2 -> release1 -> hold1，因为卖是要后于买的，而第二次交易也是后于第一次交易的，通过这个顺序我们能用这些变量自身来记录上次的值。相当于release2的时间点要先于hold1四个点。

Prices      3    1    2    8    3    1    9    6
release2    0    0    1    7    7    7    1    1
hold2      -3   -1   -1   -1    4    6    1    1
release1    0    0    1    7    7    7    1    1
hold1      -3   -1   -1   -1   -1   -1    3    3

public class Solution {
    public int maxProfit(int[] prices) {
        int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE;
        int release1 = 0, release2 = 0;
        for(int i = 0; i < prices.length; i++){
            //在该价格点卖出第二笔股票后手里剩的钱，等于上一轮买入第二笔股票后手里剩的钱加上卖出当前股票价格的钱，或者上一轮卖出第二笔股票后手里剩的钱两者中较大的
            release2 = Math.max(release2, hold2 + prices[i]);
            //在该价格点买入第二笔股票后手里剩的钱，等于上一轮卖出第一笔股票后手里剩的钱减去买入当前股票价格的钱，或者上一轮买入第二笔股票后手里剩的钱两者中较大的
            hold2 = Math.max(hold2, release1 - prices[i]);
            //在该价格点卖出第一笔股票后手里剩的钱，等于上一轮买入第一笔股票后手里剩的钱加上卖出当前股票价格的钱，或者上一轮卖出第一笔股票后手里剩的钱两者中较大的
            release1 = Math.max(release1, hold1 + prices[i]);
            //在该价格点买入第一笔股票后手里剩的钱，等于初始资金减去买入当前股票价格的钱或者初始资金（不买）中较大的
            hold1 = Math.max(hold1, -prices[i]);
        }
        return release2;
    }
}

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.
Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

时间 O(Nk) 空间 O(Nk)

我们将第i天已经执行j笔交易的最大收益作为全局变量global，将第i天正好完成第j笔交易的最大收益作为局部变量local。

对于global，也就是我们要知道第i天已经执行j笔交易的最大收益，可以基于第i-1天已经执行j笔交易的最大收益和第i天正好完成第j笔交易的最大收益，即globali = max(globali-1, locali)。

对于local，也就是我们要知道第i天正好完成第j笔交易的最大收益，可以基于第i-1天正好完成第j-1笔交易的最大收益加上当天交易的差值，还有第i-1天正好完成第j笔交易的最大收益加上当天交易的差值。要注意的是，第i-1天正好完成第j-1笔交易这种情况，当前交易的差值取0和实际昨天今天差价中较大的，因为我们还有一次自由交易的余地，所以如果亏的话完全可以当天买卖避免损失。但第i-1天正好完成第j笔交易这种情况来推导第i天正好完成第j笔交易时，相当于第i天已经要连着第i-1天交易，使得第i-1天正好完成的第j笔交易和第i天正好完成的第j笔交易是同一个交易。算式是：locali = max(locali-1+max(0, diff), locali-1+diff)

对于k > prices.length / 2的情况，我们可以用II的解法来节省空间。因为按照题意必须先买后卖，那么对于n天交易，能够产生有效收益的交易次数是小于等于n/2的，只有不同天买卖才能产生差价。对于大于n/2的那部分交易，必定是当天买卖没有任何收益的，无论交易多少次都是一样的。所以如果k > prices.length / 2，就相当于无限次交易。

数组的第二维初始化长度是k+1，因为我们要预留完成0笔交易的收益，是0。

public class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices.length == 0) return 0;
        //用II的解法优化k > prices.length / 2的情况
        if(k > prices.length / 2){
            int sum = 0;
            for(int i = 1; i < prices.length; i++){
                if(prices[i]>prices[i-1]) sum += prices[i] - prices[i-1];
            }
            return sum;
        }
        //初始化全局变量和局部变量
        int[][] global = new int[prices.length][k+1];
        int[][] local = new int[prices.length][k+1];
        for(int i = 1; i < prices.length; i++){
            int diff = prices[i] - prices[i-1];
            for(int j = 1; j < k + 1; j++){
                //更新局部变量
                local[i][j] = Math.max(global[i-1][j-1]+Math.max(0, diff), local[i-1][j]+diff);
                //更新全局变量
                global[i][j] = Math.max(global[i-1][j], local[i][j]);
            }
        }
        return global[prices.length - 1][k];
    }
}

时间 O(N) 空间 O(k)

这个解法和III中滚动扫描法是一样的，区别在于III我们用了固定的四个变量来记录两次交易，而IV中我们需要2k个变量来记录k次交易。

数组长度要初始为k+1，这样方便我们处理第一笔交易的情况。

public class Solution {
    public int maxProfit(int k, int[] prices) {
        //用II的解法优化k > prices.length / 2的情况
        if(k > prices.length / 2){
            int sum = 0;
            for(int i = 1; i < prices.length; i++){
                if(prices[i]>prices[i-1]) sum += prices[i] - prices[i-1];
            }
            return sum;
        }
        //初始化买卖股票后剩余金钱的数组
        int[] release = new int[k+1];
        int[] hold = new int[k+1];
        for(int i = 0; i < k+1; i++){
            hold[i]=Integer.MIN_VALUE;
        }
        for(int i = 0; i < prices.length; i++){
            for(int j = 1; j < k+1; j++){
                //卖出第j笔交易，所剩余的钱
                release[j] = Math.max(release[j], hold[j]+prices[i]);
                //买入第j笔交易，所剩余的钱
                hold[j] = Math.max(hold[j], release[j-1]-prices[i]);
            }
        }
        return release[k];
    }
}

Q：如果对于每个时间点，都可以买入1次，而对于每个时间点，都可以卖出之前持有的任意多个股票，该如何计算？
A：因为可以持续持有多个之前买的股票，我们可以一直买入并持有，直到第一个全局最高点时再一起卖出去。接着我们再一直买入，直到剩余价格中的全局最高点时卖出去，以此类推。这里提供两个解题思路：

先遍历一遍找出所有峰值，并将这些峰值和他们的坐标打包起来，扔进一个Heap。这样再从头遍历一遍，先拿出堆顶，把直到堆顶坐标之前的差值都累加起来，过了这个堆顶的坐标后再看下一个有效堆顶（有效堆顶是指下标在当前下标之后的）。时间复杂度O(NlogN)。

先找出全局最高点，然后在整个数组之前加一个最大值元素，这样就把这道题转换成了积水问题。时间复杂度O(N)。

Q: 如果每次交易有手续费怎么办？
A: 手续费实际上就是降低了卖价（或者等同于提高了买价），我们根据手续费相应调整利润就行了。