【2023】字节跳动 10 日心动计划——第四关

1. 买卖股票的最佳时机

假设在第 i i i 天卖出股票可获得最大利润，那么买入股票必然是在前 i − 1 i-1 i−1 天中的某一天。更进一步，买入股票应当是第 arg min ⁡ 0 ≤ x ≤ i − 2 a [ x ] \argmin_{0\leq x\leq i-2} a[x] argmin0≤x≤i−2​a[x] 天。这说明我们可以维护一个 minprice 的变量，这样一来，a[i] - minprice 就代表在第 i i i 天卖出股票能够获得的最大利润。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minprice = 1e9;
        int ans = 0;
        for (auto& price: prices) {
            minprice = min(minprice, price);
            ans = max(ans, price - minprice);
        }
        return ans;
    }
};

2. 打家劫舍 II

先回顾第一代的打家劫舍。

考虑使用dp。我们用 dp[i] 来代表偷前 i i i 家能够获得的最大金额，那么我们可以按照第 i i i 个元素的情况对 dp[i] 进行划分。

• 偷窃第 i i i 间房屋，那么就不能偷窃第 i − 1 i-1 i−1 间房屋，偷窃总金额为前 i − 2 i-2 i−2 间房屋的最高总金额与第 i i i 间房屋的金额之和。
• 不偷窃第 i i i 间房屋，偷窃总金额为前 i − 1 i-1 i−1 间房屋的最高总金额。

转移方程为：

d p [ i ] = m a x ( d p [ i − 2 ] + n u m s [ i ] ,   d p [ i − 1 ] ) dp[i]=max(dp[i-2]+nums[i], \,dp[i-1]) dp[i]=max(dp[i−2]+nums[i],dp[i−1])

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        vector<int> dp(n);

        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        return dp[n - 1];
    }
};

下面回到本题。

假如偷第 0 0 0 间房屋，那么剩下可以偷窃的范围就是 [ 2 , n − 2 ] [2,n-2] [2,n−2]；假如不偷第 0 0 0 间房屋，那么剩下可以偷窃的范围就是 [ 1 , n − 1 ] [1,n-1] [1,n−1]。取两者中的最大值就是本题答案。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        if (n == 2) return max(nums[0], nums[1]);

        vector<int> a(nums.begin() + 2, nums.begin() + n - 1);
        int price1 = rob1(a) + nums[0];

        vector<int> b(nums.begin() + 1, nums.begin() + n);
        int price2 = rob1(b);

        return max(price1, price2);
    }

    int rob1(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];

        vector<int> dp(n);

        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);

        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }

        return dp[n - 1];
    }
};

此外，还可以使用滚动数组将空间复杂度优化至 O ( 1 ) O(1) O(1)，这里从略。