2018-11-17

Leetcode

11 minutes read (About 1643 words) 0 visits

Leetcode 188. Best Time to Buy and Sell Stock

本题有四个不同难度的版本：

下面分题进行讲解：

121. Best Time to Buy and Sell Stock

Difficulty: Easy
Total Accepted: 379.2K
Total Submissions: 843.6K

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:

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:

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

解题思路

本题要求很简单，对于一个价格波动的股票，我们需要找到一个买入点和一个卖出点，使得最终收益最大化。因而我们只需要创建一个数组，存储从一开始到第 i 个价格的最低价格，然后用当前价格减去它，即可得到当前卖出的最大收益，并最终得到全局卖出的最大收益。

题解（最优解）

static const auto runfirst = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        int *minPrice = new int[size];
        int maxProfit = 0;
        if (size) {
            minPrice[0] = prices[0];
            for (int i = 1; i < size; ++i) {
                minPrice[i] = min(minPrice[i-1], prices[i]);
                maxProfit = max(maxProfit, prices[i] - minPrice[i]);
            }
        }
        
        return maxProfit;
    }
};

122. Best Time to Buy and Sell Stock II

Difficulty: Easy
Total Accepted: 258.8K
Total Submissions: 520.4K

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

Example 1:

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:

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:

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

解题思路

本题相比上题只是多了一个「可任意次数买卖的条件」，不过这对我们而言反而是一件好事。因为由此一来，我们实际上可以赚取到理论最大收益，所以我们只需要统计所有股票涨的价格即可。

题解（最优解）

static const auto runfirst = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int size = prices.size();
        int *minPrice = new int[size];
        int maxProfit = 0;
        for (int i = 1; i < size; ++i) {
            if (prices[i] > prices[i - 1]) {
                maxProfit += prices[i] - prices[i - 1];
            }
        }
        return maxProfit;
    }
};

123. Best Time to Buy and Sell Stock III

Difficulty: Hard
Total Accepted: 127.2K
Total Submissions: 398.0K

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:

Input: [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:

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:

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

解题思路

本题相对要复杂些，题目将交易的次数限制为两次，所以我们不能单纯地去找最优的那一次。所以我们实际上需要去寻找两个不交叉的交易段，也就是一共四个时间点（买入1、买入2、卖出1、卖出2）。进一步想，我们可以如此维护这四个变量：

若当前价格使得买入后财富损失最小，则记录当前值
若当前价格使得在 1 的前提下卖出收益最大，则记录当前值
若当前价格使得在 2 的前提下买入综合收益最大，则记录当前值
若当前价格使得在 3 的前提下卖出综合收益最大，则记录当前值

最后在步骤四记录的价格便是本题结果了。为什么我们可以这样做呢？实际上，我们在步骤四中维护的值是「在之前的某点第一次卖出后，所能获取的最大的收益」，是一个全局最优值。至于证明过程就留给各位读者自行解决了。

题解（最优解）

static const auto runfirst = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() < 2) return 0;
        int buy1 = INT_MIN, 
            buy2 = INT_MIN, 
            sell1 = 0, 
            sell2 = 0;
        for (auto& price : prices) {
            sell2 = max(buy2 + price, sell2);
            buy2 = max(sell1 - price, buy2);
            sell1 = max(buy1 + price, sell1);
            buy1 = max(-price, buy1);
        }
        
        return (sell2 > 0) ? sell2 : 0;
    }
};

188. Best Time to Buy and Sell Stock IV

Difficulty: Hard
Total Accepted: 133K
Total Submissions: 520K

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

Example 1:

Input: [2,4,1], k = 2
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

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

解题思路

实际上是上一题的拓展，我们只需要把上一题固定的变量数量变为可变的就可以求解得出了。但是需要注意的是，直接如此使用可能会导致内存爆炸，建议加一个在 k 足够大时，调用前面第二题的方法的逻辑

题解（最优解）

static const auto runfirst = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return nullptr;
}();

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if (prices.size() < 2) return 0;
        if (k < 1) return 0;
        if (k * 2 > prices.size()) return easyAdd(prices);
        vector<int> buys;
        vector<int> sells;
        
        for (int i = 0; i < k; ++i) {
            buys.push_back(INT_MIN);
            sells.push_back(0);
        }
        
        for (auto& price : prices) {
            buys[0] = max(-price, buys[0]);
            for (auto iter1 = buys.begin(),
                iter2 = sells.begin();
                iter1 != buys.end();) {
                *iter2 = max(*iter2, *(iter1++) + price);
                *iter1 = max(*iter1, *(iter2++) - price);
            }
            *(sells.rbegin()) = max(*(sells.rbegin()), *(buys.rbegin()) + price);
        }
        
        return *(sells.rbegin());
    }
    
    int easyAdd(vector<int>& prices) {
        int sum = 0;
        int previousPrice = prices[0];
        for (auto& price : prices) {
            sum += max(price - previousPrice, 0);
            previousPrice = price;
        }
        return sum;
    }
};