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.

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 (i.e., you must sell the stock before you buy again).
Example 1:

1
2
3
4
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than buying price.

Example 2:

1
2
3
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

解决思路

可以用动态规划的思想，buy代表买入后的资金（肯定是负数，因为买入话要钱，还没有收益），sell代表卖出后的基金

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxProfit(int[] prices) {
        int sell = 0, buy = Integer.MAX_VALUE;
        for (int i = 0; i < prices.length; i++) {
            buy = Math.min(buy, prices[i]);
            sell = Math.max(sell, prices[i] - buy);
        }
        return sell;
    }
}

Best Time to Buy and Sell Stock II

问题描述

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 (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

解决思路

只要计算 所有上升高度差 的和就可以了。

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxProfit(int[] prices) {
        int count = 0;
        for (int i=1;i<prices.length;i++){
            if (prices[i]>prices[i-1])
                count += prices[i] - prices[i-1];
        }
        return count;
    }
}

Best Time to Buy and Sell Stock III

问题描述

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 (i.e., you must sell the stock before you buy again).

解决思路1-solution!)

首先假设我们没有钱，所以buy1代表我们得和别人借钱，所以我们希望我们可以尽可能少的借钱，即prices[i]最小。而buy1代表现在有多少钱，是负的所以使-prices[i]最大；

sell1意味着我们决定第一次出售股票后有多少钱。是卖出的价格-买入的价格，也是出售股票前手里的钱+卖股票的钱=buy1 + prices[i]；

buy2意味着我们想买另一只股票，因此我们已经卖出了1笔钱，所以在买入stock2之后，我们有buy2 = sell1 - price [i]剩下的钱；

sell2表示我们卖出股票stock2后最终拥有的钱，也是我们可以拥有的最多钱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProfit(int[] prices) {
        int buy1 = Integer.MIN_VALUE;  //第一次买入后我们剩下的钱（负数）
        int buy2 = Integer.MIN_VALUE;  //第一次卖出剩下的钱
        int sell1 = 0;  //第二次买入后我们剩下的钱
        int sell2 = 0;  //第二次卖出剩下的钱
        for (int i=0;i<prices.length;i++){
            buy1 = Math.max(buy1 , -prices[i]);
            sell1 = Math.max(sell1 , buy1 + prices[i]);
            buy2 = Math.max(buy2 , sell1 - prices[i]);
            sell2 = Math.max(sell2 , buy2 + prices[i]);
        }
        return sell2;
    }
}

Best Time to Buy and Sell Stock III

问题描诉

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.

解决思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length<=1 || k==0)
            return 0;
        
        if(k > prices.length/2){   //如果k太大了，那就可以用第二个问题的思路来解决
            int res = 0;
            for(int i=1;i<prices.length;i++)
                if(prices[i]>prices[i-1])
                    res += prices[i] - prices[i-1];
            return res;
        }
        
        int[] buy = new int[k];
        int[] sell = new int[k];
        for(int i=0;i<k;i++){  //初始化数组
            buy[i] = Integer.MIN_VALUE;
            sell[i] = 0;
        }
        
        for(int i=0;i<prices.length;i++){
            buy[0] = Math.max(buy[0], -prices[i]);   //第一次购买前没有卖出
            sell[0] = Math.max(sell[0], buy[0] + prices[i]);
            for(int j=1;j<k;j++){
                buy[j] = Math.max(buy[j], sell[j-1] - prices[i]);  // hold->hold, sold->hold
                sell[j] = Math.max(sell[j], buy[j] + prices[i]);  // sold->sold, hold->sold
            }
        }
        return sell[k-1];
    }
}

309. Best Time to Buy and Sell Stock with Cooldown

问题描述

解决思路2

买入的前一天必须是休息，最后一天如果要是买入，那最后还需要消耗一笔金钱，这笔金钱是当日的股票价price，那么方程是：

1
buy[i] = max{rest[i-1]-price, buy[i-1]}

卖出的前一天必须是买入，最后一天卖出后，会多得到当日的股价price，那么方程是：

1
sell[i] = max{buy[i-1]+price, sell[i-1]}

休息的话有多种情况，最后一天休息的话，前一天可以是买入、卖出或者休息，且最后一天也不会有进账或者消费，那么方程是：

1
rest[i] = max{buy[i-1], sell[i-1], rest[i-1]}

但是稍微想一下就知道，最后一天买入后的收益一定小于最后一天休息的收益，由小于最后一天卖出的收益，即：

1
buy[i] <= rest[i] <= sell[i]

那么我们rest的方程就可以变为：

1
rest[i] = sell[i-1]

代入buy和sell的方程就是：

1
2
3
buy[i] = max{sell[i-2]-price, buy[i-1]}

sell[i] = max{buy[i-1]+price, sell[i-1]}

由于每次计算第i个值时我们只用到了最多前两个sell和前一个buy，所以我们不需要记录整个数组的buy和sell，将空间复杂度降低到O（1），只需要记录前两个sell和前一个buy，根据代码的写法，我们甚至只需要记录前一个sell，将对sell的计算放在buy之后，那么自然而然就变成前两个sell了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int maxProfit(int[] prices) {
        int buy = Integer.MIN_VALUE;
        int sell = 0;
        int pre_buy = 0;
        int pre_sell = 0;
        for(int i=0;i<prices.length;i++){
            pre_buy = buy;
            buy  = Math.max(pre_buy, pre_sell - prices[i]);
            pre_sell = sell;
            sell = Math.max(pre_sell, pre_buy + prices[i]);
        }
        return sell;
    }
}

Best Time to Buy and Sell Stock with Transaction Fee

问题描述

Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

1
2
3
4
5
6
7
8
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
- Buying at prices[0] = 1
- Selling at prices[3] = 8
- Buying at prices[4] = 4
- Selling at prices[5] = 9
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

解决思路

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int buy = Integer.MIN_VALUE;
        int sell = 0;
        for(int i=0;i<prices.length;i++){
            buy = Math.max(buy, sell - prices[i] - fee);
            sell = Math.max(sell, buy + prices[i]);
        }
        return sell;
    }
}