细语呢喃

技术改变生活

0%

leetcode Best Time to Buy and Sell Stock

发表于 分类于 ， 阅读次数： 评论数：

本次题解包括

  • 121 Best Time to Buy and Sell Stock
  • 122 Best Time to Buy and Sell Stock II
  • 123 Best Time to Buy and Sell Stock III
  • 188 Best Time to Buy and Sell Stock IV
  • 714. Best Time to Buy and Sell Stock with Transaction Fee

121 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 (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

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.

传送门

题意：给定股票每日的售价，求 一次买进和一次卖出最多可以获取多大利润？

思路：其实就是求买进时和卖出是最大差价。每次更新当前最小价格，dp即可。

python

1
2
3
4
5
6
7
8
9
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices: return 0
        min_v = prices[0]
        ans = 0
        for i, price in enumerate(prices):
            ans = max(ans, price - min_v)
            min_v = min(price, min_v)
        return ans

 

122 Best Time to Buy and Sell Stock II

Say you have an array prices 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).

Example 1:

1
2
3
4
Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
             Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

1
2
3
4
5
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
             Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
             engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

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

Constraints:

  • 1 <= prices.length <= 3 * 10 ^ 4
  • 0 <= prices[i] <= 10 ^ 4

传送门

题意：给定股票每日的售价，求 若干次买卖最多可以获取多大利润？

思路：其实就是求股票低价买，高价卖最多能获得多少钱。求连续上升的高度和。

如12314为 1买进3卖出1买进4卖出。

python

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices : return 0
        ans, money, n = 0, prices[0], len(prices)
        i = 0 
        while i < n:
            money = prices[i]
            while i + 1 < n and prices[i] <= prices[i + 1]:
                i += 1
            ans += prices[i] - money
            i +=1
        return ans

 还可以这么写：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        if not prices : return 0
        ans = 0
        for i in xrange(1,len(prices)):
            if prices[i] > prices[i-1] :
                ans += prices[i] - prices[i-1]

        return ans

 c++版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for (int i = 0; i < prices.size(); ) {
            int j = i + 1;
            while(j < prices.size() && prices[j] >= prices[j - 1]) {
                ++j;
            }
            --j;
            ans += prices[j] - prices[i];
            i = j + 1;
        }
        return ans;
    }
};

123 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).

Example 1:

1
2
3
4
Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

1
2
3
4
Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

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

Example 4:

1
2
Input: prices = [1]
Output: 0

Constraints:

  • 1 <= prices.length <= 10^5
  • 0 <= prices[i] <= 10^5

题目地址：Best Time to Buy and Sell Stock III

题意:给定股票每日的售价，求最多两次买卖最多可以获取多大利润？

思路：

方法一：两遍DP

设dp[i]为到第i天能获取的最大值。（类似121题）求出dp后，逆向扫描数组。

nax_price为最大售价，每次减去price[i]得到第i天之后的利润，加上dp[i - 1]即为两次买卖的值。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;
        vector<int> dp(prices.size(), 0);
        int min_price = prices[0];
        for(int i = 1; i < prices.size(); ++i){
            dp[i] = max(dp[i - 1], prices[i] - min_price);
            min_price = min(prices[i], min_price);
        }
        int ans = dp.back();
        int max_price = prices.back();
        for(int i = prices.size() - 2; i >= 1; --i){
            ans = max(ans, max_price - prices[i] + dp[i - 1]);
            max_price = max(max_price, prices[i]);
        }
        return ans;
    }
};

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices: return 0
        dp = [0] * len(prices)
        min_price = prices[0]
        for i in range(1, len(prices)):
            dp[i] = max(dp[i - 1], prices[i] - min_price)
            min_price = min(prices[i], min_price)
        
        ans = dp[-1]
        max_price = prices[-1]
        for i in range(len(prices) - 2, 0, -1):
            ans = max(ans, max_price - prices[i] + dp[i - 1])
            max_price = max(max_price, prices[i])
            
        return ans

 

方法2：直接dp

设buy1[i]]为累计到i天买入一次最大的收益，sell1[i]为i天内卖出一次最大收益

buy2[i]为累积到第i天买入两次最大收益，sell2[i]为i天内共卖出两次最大收益

容易有下面的状态转移方程

  • buy1[i] = max(buy1[i - 1], -prices[i]);

  • sell1[i] = max(sell1[i - 1], buy1[i - 1] + prices[i]);

  • buy2[i] = max(buy2[i - 1], sell1[i - 1] - prices[i]);

  • sell2[i] = max(sell2[i - 1], buy2[i - 1] + prices[i]);

初始化的时候，buy1[0] = -prices[0]这个比较好理解，而buy2[0] = -prices[0]这个可以理解为一天内买入卖出在买入。

最后，答案为max(0, sell1[-1], sell2[-1])这几个中，但是由于buy2的公式必定不小于buy1, sell2也必然不小于sell1，而sell2初始化为0，取的max更新，因此最后答案就是sell2[-1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        vector<int> buy1(prices.size(), 0);
        vector<int> buy2(prices.size(), 0);
        vector<int> sell1(prices.size(), 0);
        vector<int> sell2(prices.size(), 0);
        buy1[0] = buy2[0] = -prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            buy1[i] = max(buy1[i - 1], -prices[i]);
            sell1[i] = max(sell1[i - 1], buy1[i - 1] + prices[i]);
            buy2[i] = max(buy2[i - 1], sell1[i - 1] - prices[i]);
            sell2[i] = max(sell2[i - 1], buy2[i - 1] + prices[i]);
        }
        return sell2.back();
    }
};

还可以进一步优化空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.empty()) return 0;
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 0; i < prices.size(); ++i) {
            sell2 = max(sell2, buy2 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);
            sell1 = max(sell1, prices[i] + buy1);
            buy1 = max(buy1, -prices[i]);
        }
        return sell2;
    }
};

188. Best Time to Buy and Sell Stock IV

Say you have an array for which the _i_th 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).

题目地址：Best Time to Buy and Sell Stock IV

题意：给定股票每日的售价，求最多k次买卖最多可以获取多大利润？

思路：dp

设dp[i][x]为第i天第x次交易的最大利润，则容易写出dp方程：

  • dp[i][x] = max(dp[i-1][x] , dp[j][x - 1] + prices[i] - prices[j])  0 <= j < i
  • 上面的状态转移方程第一项为第i天不进行交易，第二项为枚举j 从0~i-1，第j天买入，第i天卖出

注意当k >= len(prices) / 2的时候，说明相当于无限次交易，和第122题Best Time to Buy and Sell Stock II 一样。

上面的复杂度为O(kn^2)代码如下:

C++ 

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
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(prices.empty()) return 0;
        int ans = 0;
        if(k >= prices.size() / 2){
            for(int i = 1; i < prices.size(); ++i){
                if(prices[i] > prices[i - 1])
                    ans += prices[i] - prices[i - 1];
            }
            return ans;
        }
        vector<vector<int>> dp(prices.size(), vector<int>(k + 1, 0));
        for(int x = 1; x <= k; ++x){
            for(int i = 1; i < prices.size(); ++i){
                dp[i][x] = dp[i - 1][x]; // 不做交易
                for(int j = 0; j < i; ++j){
                    dp[i][x] = max(dp[i][x], dp[j][x - 1] + prices[i] - prices[j]);
                }
            }
            ans = max(ans, dp[prices.size() - 1][x]);
        }
        return ans;
    }
};

 

可以对上面的代码优化，注意到枚举j是为了寻找第i天之前交易x-1次的利润最大，而这个过程重复计算了很多，可以进行优化，只需要保存i之前最大的dp[j][x - 1] - prices[j]即可。这样复杂度就变为O(nk)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(prices.empty()) return 0;
        int ans = 0;
        if(k >= prices.size() / 2){
            for(int i = 1; i < prices.size(); ++i){
                if(prices[i] > prices[i - 1])
                    ans += prices[i] - prices[i - 1];
            }
            return ans;
        }
        vector<vector<int>> dp(prices.size(), vector<int>(k + 1, 0));
        for(int x = 1; x <= k; ++x){
            int max_pre = -prices[0]; //+ dp[0][x - 1];
            for(int i = 1; i < prices.size(); ++i){
                dp[i][x] = max(dp[i - 1][x], max_pre + prices[i]);
                max_pre = max(max_pre, dp[i][x - 1] - prices[i]);
            }
            ans = max(ans, dp[prices.size() - 1][x]);
        }
        return ans;
    }
};

空间复杂度上也可以进一步优化为O(n)

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
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(prices.empty()) return 0;
        int ans = 0;
        if(k >= prices.size() / 2){
            for(int i = 1; i < prices.size(); ++i){
                if(prices[i] > prices[i - 1])
                    ans += prices[i] - prices[i - 1];
            }
            return ans;
        }
        vector<int> dp(prices.size(), 0);
        for(int x = 1; x <= k; ++x){
            vector<int> ndp(prices.size(), 0);
            int max_pre = -prices[0];
            for(int i = 1; i < prices.size(); ++i){
                ndp[i] = max(ndp[i - 1], max_pre + prices[i]);
                max_pre = max(max_pre, dp[i] - prices[i]);
            }
            ans = max(ans, ndp.back());
            dp = ndp;
        }
        return ans;
    }
};

 

之前的写法：

dp,设dp[i][j]为第J天进行第i次交易能获取的最大值。

  • 当k >=n/2时候，相当于第122题。Best Time to Buy and Sell Stock II
  • dp[i][j]=max(dp[i][j-1],prices[j] + maxTemp)  我们能获取的最大利润，当我们在第j天进行抛售时。由于maxTemp已经算了买进时的价格，所以直接加上即可。
  • maxTemp =max(maxTemp,dp[i-1][j-1] - prices[j])  可以理解为已获得的最大利润，即如果买进第j天的，那么用之前一轮的买卖，前一天的的利润即（dp[i-1][j-1]）减去prices[j]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    # @return an integer as the maximum profit 
    def maxProfit(self, k, prices):
        n = len(prices)
        if k >= (n>>1):return self.maxProfit2(prices)
        dp =[[0 for j in xrange(n)]for i in xrange(k+1)]

        for i in xrange(1,k+1):
            maxTemp=-prices[0]
            for j in xrange(1,n):
                dp[i][j]=max(dp[i][j-1],prices[j] + maxTemp)
                maxTemp =max(maxTemp,dp[i-1][j-1] - prices[j])
        return dp[k][n-1]

    def maxProfit2(self,prices):
        ans = 0
        for i in xrange(1,len(prices)):
            if prices[i]>prices[i-1]:
                ans +=prices[i]-prices[i-1]
        return ans

 

714. 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.

Example 1:

1
2
3
4
5
6
7
8
9
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.

Note:

  • 0 < prices.length <= 50000.
  • 0 < prices[i] < 50000.
  • 0 <= fee < 50000.

题目地址：leetcode Best Time to Buy and Sell Stock with Transaction Fee

题目大意：给定股票的价格，以及每次交易需要的花费fee，求能获得的最大利润

思路：

双状态DP，类似于Best Time to Buy and Sell Stock with Cooldown

sell 考虑第i天是否卖出，buy考虑第i天是否买入

则有：

  • sell = max(sell, buy + prices[i] - fee)
  • buy = max(buy, sell - prices[i])

C++ 

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        if(prices.size() < 2) return 0;
        int sell = 0, buy = -prices[0];
        for(int i = 1; i < prices.size(); i++){
            sell = max(sell, buy + prices[i] - fee);
            buy = max(buy, sell - prices[i]);
        }
        return sell;
    }
};

Java 

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

Python 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def maxProfit(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        if len(prices) < 2: return 0
        sell = 0
        buy = -prices[0]
        for i in range(1, len(prices)):
            sell = max(sell, buy + prices[i] - fee)
            buy = max(buy, sell - prices[i])
        return sell

本文是leetcode如下的题解

更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~