【动态规划】（二）线性动态规划之带维度单串问题

带维度单串问题

上一篇中的单串问题，子问题仅与位置 i 有关，也就是 dp[i] 的问题。在此基础上，如果子问题还与某种指标 k 有关，k 的物理意义比较常见的有长度，个数，次数，颜色等，则是另一大类问题，状态通常写成 $dp[i][k]$。其中 k 上可能有二分，贪心等算法。这类问题相比于普通单串问题要更复杂，需要多见多积累。

1 经典问题：最大平均值和的分组

问题描述：

给定数组 nums 和一个整数 k 。我们将给定的数组 nums 分成最多 k 个相邻的非空子数组 。 分数由每个子数组内的平均值的总和构成。

注意我们必须使用 nums 数组中的每一个数进行分组，并且分数不一定需要是整数。

返回我们所能得到的最大分数是多少。

我们用 $dp[i][k]$ 表示把数组 nums[i…n-1] 分成 k 个区间所能取得的最大分数，于是 $dp[i][k]$ 在状态转移时取决于 $dp[j][k-1]$ 和 $avg(i,j-1)$，其中$j>i$，$avg(i,j-1)$表示从 i 到 j-1 区间内的平均值，也就是把数组 nums[i…n-1] 分成 k 个区间所能取得的最大分数取决于把数组 nums[j…n-1] （j > i）分成 k-1 个区间取得的最大分数加上从 nums[i] 到 nums[j-1] 的平均值。于是可以写出状态转移方程：

dp[i][k] = dp[j][k-1] + avg(i, j-1);

可以看出，k状态的推导与 k-1 状态有关，因此我们先从小到大枚举k，k=1时，$dp[i][1]$相当于不划分子区间，也就是从nums[i] 到 nums[n-1] 的平均值。在每一次枚举k时，也就相当于一个单独的单串问题，枚举 i 和 j 进行状态转移即可。

因为 k 状态的推导只与 k-1 状态有关，所以利用滚动数组的思想，不需要使用二维数组存储状态信息，只用一维数组即可，因为我们从小到大遍历位置 i ，每次状态转移时，比 i 大的位置 dp[j] 还存储着 k-1 时的状态，然后我们利用这个状态更新 dp[i] ，此时 dp[i] 就被更新到了 k 状态。

另外计算区间平均值可以利用前缀和，避免重复计算，可以在O(1)时间内算出区间平均值。

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int K) {
        // 前缀和方便快速计算区间平均值
        int n = nums.size();
        vector<double> sums(n + 1);
        for (int i = 0; i < n; ++i)
        {
            sums[i+1] = sums[i] + nums[i];
        }

        //第k次推导只与k-1的状态有关，因此只用一维数组就可以
        vector<double> dp(n);
        // 初始化，相当于k=1的情况，初始化dp[i][1]
        for (int i = 0; i < n; ++i)
        {
            dp[i] = (sums[n]-sums[i])/double(n-i);
        }

        for (int k = 2; k <= K; ++k)    //为了好理解k从2开始枚举，实际上无所谓
        {
            //普通的单串问题
            for (int i = 0; i < n; ++i)
            {
                for (int j = i+1; j < n; ++j)
                {
                    dp[i] = max(dp[i], (sums[j]-sums[i])/(j-i) + dp[j]);
                }
            }
        }
        return dp[0];
    }
};

2 经典问题：股票系列

股票系列问题是 $dp[i][k]$ 这种状态设计模式的经典问题。同时还包含更复杂的情况 $dp[i][k][state]$ .

买卖股票的最佳时机

问题描述：

给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。
你可以在某一天买入，在之后的某一天卖出，返回你能获得的最大利润 。

股票系列的入门问题，只能买卖一次股票，因此只是一个简单的单串问题，第 k 天能够获得的最大利润只与第 k-1 天能获得的最大利润有关：

dp[k] = max(dp[k-1], prices[k] - minprice)

当然因为这道题非常简单，一次遍历记录 minprice 和 maxprofits就可以解决。

买卖股票的最佳时机 II

问题描述：

给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。

这次我们可以多次买卖股票，但同一时间只能最多持有一股股票。

因此每天我们都只可能有两种状态，一种是持有股票，一种是不持有股票。于是定义状态 $dp[i][0]$ 表示第 i 天交易完后手里没有股票的最大利润，$dp[i][1]$表示第 i 天交易完后手里持有1股股票的最大利润。分别考虑这两种状态如何转移即可。

• 如果第 i 天交易完后手里没有股票，那么那么可能的转移状态为前一天已经没有股票，即 $dp[i-1][0]$，或者前一天结束的时候手里持有一股股票，即$dp[i-1][1]$，这时候我们要将其卖出，并获得 $prices[i]$ 的收益。因此为了收益最大化，我们列出如下的转移方程：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])

• 如果第 i 天交易完后手里有1股股票，那么那么可能的转移状态为前一天已经有1股股票，即 $dp[i-1][1]$，或者前一天结束的时候手里没有股票，即$dp[i-1][0]$，这时候我们要买入1股，所以总利润要减去今天的股票价格 $prices[i]$。因此可以列出如下的转移方程：

dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])

对于初始状态，根据状态的定义，我们可以知道第 0 天交易结束的时候 $dp[0][0]=0$， $dp[0][1]=-prices[0]$。

由于全部交易结束后，持有股票的收益一定低于不持有股票的收益，所以最终结果返回 $dp[n-1][0]$即可。

另外，本题使用贪心算法会更简单，但不容易想到，不过这道题中我们可以用动态规划推导出贪心算法。

动态规划的状态定义定义和上面的方法稍有不同，定义状态 $dp[i][0]$ 表示第 i 天交易完后手里没有股票的最大纯利润，$dp[i][1]$表示第 i 天交易完后手里持有1股股票的最大纯利润。什么是纯利润呢，也就是我们不考虑买入和卖出股票本身的花费，只考虑买入和卖出时，所获得的股票差价。比如第一天买入时价格是7，第二天卖出时价格是1，我们的纯利润就是-6。 所以按照这个状态定义，初始状态 $dp[0][0]$ 和 $dp[0][1]$ 都是0。然后我们可以重新考虑这次状态该如何转移：

• 如果第 i 天交易完后手里没有股票，那么可能的情况是前一天已经没有股票，那么今天的纯利润就是前一天的纯利润，即 $dp[i-1][0]$，因为今天什么操作都没做；另一种情况是前一天结束的时候手里持有一股股票，即$dp[i-1][1]$，这时候我们要将其卖出，卖出后我们获得的纯利润是 $prices[i] - prices[i-1]$，于是今天的纯利润就是前一天持有1股股票的纯利润加上今天卖出后的纯利润。因此可以写出状态转移方程：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - prices[i-1])

• 如果第 i 天交易完后手里持有1股股票，那么可能的情况是前一天就持有1股股票，并且今天我们不卖出，那么到今天为止我们应该得到的纯利润，就是前一天的纯利润加上今天和昨天的差价，虽然我们今天没有卖出，但是还是要知道今天我们的盈亏是多少，因为每一天的盈亏加起来就是之后某一天卖出的时候我们能获得的纯利润；另一种情况就是前一天没有持有股票，今天买入，那么今天获得的纯利润就是前一天的纯利润，因为今天只是买入一股股票，也并没有收益，因此我们可以写出状态转移方程：

dp[i][1] = max(dp[i-1][0], dp[i-1][1] + prices[i] - prices[i-1])

神奇事情发生了，两种情况的状态转移方程一模一样，那就说明无论我们今天是否卖出，对于我们能获得的纯利润这一个属性来说，都是一样的，要么是前一天不持股时的纯利润，要么是前一天持股的纯利润加上昨天和今天股票的差价，这二者取最大值就是我们到今天为止获得的最大纯利润。

于是状态方程可以改写为：

dp = max(dp, dp + prices[i] - prices[i-1])

因为$dp[i][0]=dp[i][1]$，那就可以都用 $dp$ 替换，也就得到了上面的方程，再改变一下写法：

dp += max(0, prices[i] - prices[i-1])

这个关系式其实代表了贪心算法的思想，那就是：要使我们最后的纯利润最大，就要保证每一天的纯利润最大。

因此我们只要计算每一天和前一天的差价，把所有不小于 0 的差价全加起来，也就是我们最终能获得的最大总利润了。这个过程我们不需要考虑实际是否买入和卖出，因为最后加起来就相当于一次性买入和卖出了。

比如题目中的例子[1, 2, 3, 4, 5]，按照贪心算法，答案很简单等于4，相当于每一天都卖出前一天再买入，但是实际的交易过程并不是进行 4 次买入和 4 次卖出，而是在第 1 天买入，第 5 天卖出。

关于贪心算法的正常推导思路，可以查看官方题解方法二。

买卖股票的最佳时机 III

问题描述：

给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。

这次我们最多可以进行 2 次交易，但同一时间只能最多持有一股股票。例如：

股票价格 [1, 2, 3, 4, 5]，我们不能在第 1 天和第 2 天接连购买股票，之后第 5 天再将它们卖出。

这一次我们不能无限次进行交易了，题目规定了最多只能交易 2 次，因此我们的状态设计要把当前交易的次数考虑进去。

在上一个股票问题中，我们定义的状态 $dp[i][state]$ 表示的是第 i 天我们持有 state 支股票（state等于0或1）时最大的利润，那么这次我们定义状态 $dp[i][k][state]$ 表示第 i 天我们已经购买了 k 次股票后手中还持有 state 支股票时的最大利润，其中 k 只能是0，1或者2，因为我们最多只能交易 2 次，也就代表最多只能两次买入股票。那么我们的状态转移将分为下面 4 种情况：

• 第 i 天已经购买了 1 次股票，手中还持有 0 支股票时的最大总利润 $dp[i][1][0]$，这种情况下有两种可能性：

  • 要么我们在第 i 天之前已经完成了一次交易（买入并卖出），并且第 i 天也没有买入， 此时最大总利润就是前一天已经购买了 1 次股票且手中持有 0 支股票时的最大总利润 $dp[i-1][1][0]$，因为我们在第 i 天什么也没有做
  • 要么我们在第 i 天之前买入了一支股票，并在第 i 天卖出，完成了 1 次交易，此时最大总利润是前一天已经购买了 1 次股票且手中持有 1 支股票时最大总利润 $dp[i-1][1][1]$ 加上卖出股票获得的 $prices[i]$

  因此 $dp[i][1][0]$ 取决于上面两种情况的较大者，于是可以写出状态转移方程：

  dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])

• 第 i 天已经购买了 1 次股票，手中还持有 1 支股票时的最大总利润 $dp[i][1][1]$，这种情况下有两种可能性：

  • 要么我们在第 i 天之前一次都没有买入股票，并在第 i 天买入，此时最大总利润就是买入股票的花费 $-prices[i]$
  • 要么我们在第 i 天之前买入了 1 支股票，并且第 i 天也不卖出，此时最大总利润就是前一天已经购买了 1 次股票且手中持有 1 支股票时最大总利润 $dp[i-1][1][1]$，因为我们什么操作都没有做

  于是可以写出状态转移方程：

  dp[i][1][1] = max(dp[i-1][1][1], -prices[i])

• 第 i 天已经购买了 2 次股票，手中还持有 0 支股票时的最大总利润 $dp[i][2][0]$，这种情况下有两种可能性：

  • 要么我们在第 i 天之前已经完成了两次交易（买入并卖出），此时我们无法再进行交易，因此最大总利润就是前一天已经完成两次交易后的最大总利润 $dp[i-1][2][0]$
  • 要么我们在第 i 天之前已经完成了 一次交易（买入并卖出），并且第 2 次购买了一只股票，然后在第 i 天卖出，完成第 2 次交易，此时最大总利润就是前一天已经购买了 2 次股票并且手中还持有 1 支股票时的最大总利润 $dp[i-1][2][1]$ 加上卖出股票获得的利润 $prices[i]$

  于是可以写出状态转移方程：

  dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i])

• 第 i 天已经购买了 2 次股票，手中还持有 1 支股票时的最大总利润 $dp[i][2][1]$，这种情况下有两种可能性：

  • 要么我们在第 i 天之前完成了一次交易并且没有再进行买入，然后在第 i 天买入，此时最大总利润就是前一天已经购买了 1 次股票并且手持 0 支股票时的最大总利润 $dp[i-1][1][0]$ 加上买股票的支出 $-prices[i]$
  • 要么我们在第 i 天之前买入了 2 支股票，并且第 i 天也不卖出，此时最大总利润就是前一天已经购买了 2 次股票并且手持 1 支股票时的最大总利润 $dp[i-1][2][1]$，因为我们什么操作都没有做

  于是可以写出状态转移方程：

  dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i])

最后返回的结果自然是最后一天已经购买了 1 次或者 2 次股票后并且手中还持有 0 支股票时的最大总利润 $dp[n-1][1][0]$ 和 $dp[n-1][2][0]$ 中的最大值。

根据上面的状态转移方程，直接可以写出代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(3, vector<int>(2, 0)));
        dp[0][1][1] = -prices[0];
        dp[0][2][1] = -prices[0];
        for(int i = 1; i < n; i++)
        {
            dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i]);
            dp[i][1][1] = max(dp[i-1][1][1], -prices[i]);
            dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i]);
            dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i]);
        }
        return max(dp[n-1][1][0], dp[n-1][2][0]);
    }
};

显然第 i 天的最大总利润只与第 i - 1 天的最大总利润有关，因此不需要使用三维数组，并且因为每一天只有 4 种状态，所以我们只需要 4 个整数就可以完成动态规划推导：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int dp10 = 0, dp11 = -prices[0];
        int dp20 = 0, dp21 = -prices[0];
        for(int i = 1; i < n; i++)
        {
            dp10 = max(dp10, dp11 + prices[i]);
            dp11 = max(dp11, - prices[i]);
            dp20 = max(dp20, dp21 + prices[i]);
            dp21 = max(dp21, dp10 - prices[i]);
        }
        return max(dp10, dp20);
    }
};

可以看到虽然推导过程很复杂，但代码非常简洁，这也正是动态规划的魅力。

买卖股票的最佳时机 IV

问题描述：

给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。

这次我们最多可以进行 k 次交易，但同一时间只能最多持有一股股票。

和上一题几乎一样，理解了上题的思路，本题没有难度，只是在状态转移时要遍历购买股票的次数 k ，而不是只有 2 次了。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(prices.size() < 2) return 0;
        int ans = 0;
        vector<vector<int>> dp(k+1, vector<int>(2, 0));
        //初始化要注意，要把第一天购买1...k次后持有1支股票的情况都初始化，和上题一样
        for(int j = 1; j <= k; j++)
        {
            dp[j][1] = -prices[0];
        }
        for(int i = 1; i < prices.size(); i++)
        {
            for(int j = 1; j <= k; j++)
            {
                dp[j][0] = max(dp[j][0], dp[j][1] + prices[i]);
                dp[j][1] = max(dp[j][1], dp[j-1][0] - prices[i]);
                ans = max(ans, dp[j][0]);	//结果是最后一天购买1...k次股票后还持有0支股票的最大利润的最大值
            }
        }
        return ans;
    }
};

最佳买卖股票时机含冷冻期

题目描述：

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

这道题是 股票问题 II 的变体，多了一个冷却期，状态的推导并不难，关键在于状态要定义好，详细可以看力扣官方题解。

买卖股票的最佳时机含手续费

问题描述：
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。

同样是 股票问题 II 的变体，现在看来非常简单。

3 粉刷房子系列

粉刷房子

问题描述：

给一排房子上色，相邻房子颜色不能相同，一共有三种可选的颜色，每个房子上每种颜色的花费不同，找到花费最小的上色方案，返回最小总花费。

因为只有三种颜色，比较简单，$dp[i][k](k = 0,1,2)$表示粉刷到第 i 间房子为止，将房间 i 粉刷成颜色 k ，最小总花费，因为只有三种颜色，因此状态转移方程为：

dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i][0]
dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i][1]
dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + costs[i][2]

也就是将房间 i 粉刷成颜色 k 的最小总花费等于当前房子粉刷成颜色 k 的花费加上前一间房子粉刷成其他两种颜色时总花费的较小者。由于房间 i 的状态只取决于房间 i-1 ，因此也不需要用矩阵存储状态，只需要两个大小为3的数组（或者6个int）就可以。

粉刷房子 II

问题描述：

给一排房子上色，相邻房子颜色不能相同，一共有 K 种可选的颜色，每个房子上每种颜色的花费不同，找到花费最小的上色方案，返回最小总花费。

现在有 K 种颜色，状态转移方程就没有上面那么简单了，我们要遍历每一种颜色 k，计算$dp[i][k]$，那么此时的状态转移方程应该变为：
$$
dp[i][k] = \min_{t=0…K,t\neq k}(dp[i-1][t]) + costs[i][k]
$$
也就是将房间 i 粉刷成颜色 k 的最小总花费等于当前房子粉刷成颜色 k 的花费加上前一间房子粉刷成除颜色 k 以外的其他 K-1 种颜色时总花费的最小者。

所以只要求出第 i-1 个房间所有花费的最小值即可，但如果当前颜色 k 刚好是第 i-1 个房间的最小花费对应的颜色，那此时就应该取第 i-1 个房间第二小的花费，所以对每一个房间求出最小花费 min1st 和第二小花费 min2nd 即可。

dp_second[j] = (dp_first[j] == min1st ? min2nd : min1st) + costs[i][j]

粉刷房子 III

有余力可以了解

4 经典问题：鸡蛋掉落

问题描述：

给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。

已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。

每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。

请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

这是一道非常经典的面试题，但是难度较大，如果是作为机试题，对动态规划和数学理论的灵活运用要求非常高，因为不仅要推导动态规划方程，还要在编码过程中对动态规划过程进行优化，否则会超时无法通过全部测试用例。而如果不用动态规划的方法，就已经达到了竞赛级别，远超出了面试难度。当然因为问题过于经典，各方大佬也想出了各种容易理解的动态规划解法。

但是作为面试题，理解这道题的思路还是非常有必要而且不是那么困难的，因为面试题通常不会像原题这样问，面试通常会直接问：100层楼给你2个鸡蛋，怎么得出最小操作次数？显然也不是让你当场计算出正确答案14次，毕竟这道题即使是知道算法的情况下去手算也相当复杂，所以更重要的是思路。

这里放几个比较容易理解的题解，方法也比较主流，可以结合起来看，熟悉思路：

鸡蛋掉落官方题解

题目理解 + 基本解法 + 进阶解法

【鸡蛋掉落】5 行代码，从求扔几次变为求多少层楼

5 其他带维度单串问题

• 抛掷硬币：比较简单的带维度单串问题

• 分割数组的最大值：与上面的最大平均值和的分组非常相似，只是把分组的平均值改成了分组的和，然后求这些分组和最大值的最小值，整体思路完全一致，状态转移方程稍有不同，另外本题用动态规划不是最优解，用贪心+二分查找的方法时空复杂度更优秀，思路也不难理解，具体可以查看分割数组的最大值官方题解方法二

• 青蛙过河：给定一个数组表示一条河上石头所在的位置，青蛙只能向前跳，且每次跳跃的距离只能是 k-1、k、k+1 其中之一，k是上一次跳跃的步数，第一次跳一步，问青蛙是是否能过河？

思路：动态规划解法比较难想，并且难优化，时空复杂度也并不友好，了解即可，这道题实际上使用记忆化搜索的方法会更好，这里顺便说一下记忆化搜索的思路，因为非常简单。

首先这显然是一个典型回溯问题，因此很自然想到使用深搜，深搜的递归代码也很好写，只要用当前位置加上跳跃距离，然后搜索石头数组看是否存在对应的石头就行了，搜索这里可以用二分查找（因为数组一定是严格递增的），也可以用哈希表，我这里使用哈希表。

class Solution {
public:
    unordered_map<int,int> map;	//在O（1）时间内找到下一次跳的石头是否存在
    bool judge(vector<int>& stones, int start, int step)
    {   
        if(stones[start] + step == stones[stones.size()-1]) return true;
        if(map.find(stones[start] + step) != map.end())
        {
            if(step > 1)
            {
                return judge(stones, map[stones[start] + step], step + 1) ||
                        judge(stones, map[stones[start] + step], step) ||
                        judge(stones, map[stones[start] + step], step - 1);
            }
            else
            {
                return judge(stones, map[stones[start] + step], step + 1) ||
                        judge(stones, map[stones[start] + step], step);
            }   
        }
        return false;
    }
    bool canCross(vector<int>& stones) {
        for(int i = 0; i < stones.size(); i++)
        {
            map[stones[i]] = i;
        }
        return judge(stones, 0, 1);
    }
};

但是这样会超时，超时的原因在于递归的时候存在重复递归，回溯的时候会有之前已经解决的子问题被重复计算，因此我们只要把每次计算的子问题的结果存下来，之后再遇到这个子问题直接返回对应的结果就行了。

class Solution {
public:
    unordered_map<int,int> map;
    vector<unordered_map<int,bool>> memo;	//存储子问题结果
    bool judge(vector<int>& stones, int start, int step)
    {   
        if(stones[start] + step == stones[stones.size()-1]) return true;
        //如果遇到已经解决过的问题，直接返回对应结果
        if(memo[start].find(step) != memo[start].end()) return memo[start][step];
        if(map.find(stones[start] + step) != map.end())
        {
            if(step > 1)
            {
                memo[start][step] = judge(stones, map[stones[start] + step], step + 1) ||
                        judge(stones, map[stones[start] + step], step) ||
                        judge(stones, map[stones[start] + step], step - 1);
            }
            else
            {
                memo[start][step] =  judge(stones, map[stones[start] + step], step + 1) ||
                        judge(stones, map[stones[start] + step], step);
            }   
        }
        return memo[start][step];
    }
    bool canCross(vector<int>& stones) {
        for(int i = 0; i < stones.size(); i++)
        {
            map[stones[i]] = i;
        }
        memo.resize(stones.size());
        return judge(stones, 0, 1);
    }
};

把哈希表换成二分查找还可以进一步降低空间复杂度。

• 安排邮筒：适当了解思路