10. 电梯钻石问题

描述：你乘坐电梯从 1 楼 到 n 楼，每层电梯门都会打开，你可以看到该层的 钻石大小。你只能拿一次钻石，拿完后不能更换。请问如何才能拿到最大的一颗钻石？

分析问题

• 你只能一次性决定是否拿钻石，一旦错过就不能回头。
• 你不知道后面的楼层会有什么样的钻石，所以要在合适的时机做决策。
• 这类似于经典的 “秘书问题”（The Secretary Problem），也称为最佳停留问题（Optimal Stopping Problem）。

解法

这个问题的最优策略是**“37% 规则”（1/e 规则）**，具体方法如下：

第一阶段（观察期）

• 前 37% 的楼层（即 m ≈ 0.37 * n，向下取整）不拿钻石，只是记录当前最大值。
• 这个阶段的目的是建立一个参考标准，大致了解钻石的大小分布情况。

第二阶段（决策期）

• 从 m+1 层开始，只要发现一个比观察期最大值还大的钻石，就立即拿下。
• 如果到了最后一层仍未发现更大的，只能拿最后一颗钻石（虽然可能不是最优，但至少保证有钻石）。

数学推导

• 采用 37% 规则 的策略，能保证在大多数情况下拿到接近最大的一颗钻石。
• 成功率大约为 37%，而随机拿一颗钻石的成功率仅为 1/n，因此该策略能显著提高拿到最大钻石的概率。

示例

假设 n = 10，即有 10 层，每层的钻石大小如下：

1楼：10
2楼：20
3楼：30
4楼：50
5楼：40
6楼：70
7楼：60
8楼：90
9楼：80
10楼：100

按照 37% 规则：

• 前 37%（1-3 层） 不拿，观察最大值为 30。
• 从 4 层开始，发现 50 > 30，立即拿下！
• 虽然 8 楼、10 楼有更大钻石，但根据规则，你已经拿了 50，所以错过了后面的钻石。

这个策略不能 100% 保证拿到最大钻石，但可以 显著提高成功概率。

推广思考

1. 如果 n 变得很大，比如 1000 层，该策略是否依然适用？

   • 是的，仍然可以用 37% 规则，只是 m ≈ 370 层观察，接下来寻找比观察期最大值更大的钻石。

2. 如果你可以额外获得一次重新选择的机会，策略如何变化？

   • 第一轮使用 37% 规则，如果没拿到特别大的，可以在 剩余楼层中重新应用 37% 规则，提高成功率。

3. 如果钻石的分布是已知的（例如，大多数大钻石在上层），如何优化策略？

   • 可以调整观察期，比如在前 50% 楼层观察，以适应不同的分布情况。

相关面试题

• “秘书问题”：如何在 n 名候选人中，选择最佳秘书？
• “停车问题”：如何在一条街道上，选择最佳停车位？
• “相亲问题”：如何在 n 次约会中，选择最合适的伴侣？

✅ 这道题考察了“最优停止策略” 和 概率思维，是一个经典的决策优化问题！