购买水果需要的最少金币数

标签: 队列 数组 动态规划 单调队列 堆（优先队列）

难度: Medium

你在一个水果超市里，货架上摆满了玲琅满目的奇珍异果。

给你一个下标从 1 开始的数组 prices ，其中 prices[i] 表示你购买第 i 个水果需要花费的金币数目。

水果超市有如下促销活动：

  • 如果你花费 price[i] 购买了水果 i ，那么后面的 i 个水果你可以免费获得。

注意 ，即使你 可以 免费获得水果 j ，你仍然可以花费 prices[j] 个金币去购买它以便能免费获得接下来的 j 个水果。

请你返回获得所有水果所需要的 最少 金币数。

示例 1：

输入：prices = [3,1,2]
输出：4
解释：你可以按如下方法获得所有水果：
- 花 3 个金币购买水果 1 ，然后免费获得水果 2 。
- 花 1 个金币购买水果 2 ，然后免费获得水果 3 。
- 免费获得水果 3 。
注意，虽然你可以免费获得水果 2 ，但你还是花 1 个金币去购买它，因为这样的总花费最少。
购买所有水果需要最少花费 4 个金币。

示例 2：

输入：prices = [1,10,1,1]
输出：2
解释：你可以按如下方法获得所有水果：
- 花 1 个金币购买水果 1 ，然后免费获得水果 2 。
- 免费获得水果 2 。
- 花 1 个金币购买水果 3 ，然后免费获得水果 4 。
- 免费获得水果 4 。
购买所有水果需要最少花费 2 个金币。

提示：

  • 1 <= prices.length <= 1000
  • 1 <= prices[i] <= 105

Submission

运行时间: 39 ms

内存: 16.3 MB

class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        n = len(prices)
        q = deque([(n + 1, 0)])  # 索引， 需要花的最少钱， 最后的能赠送最好  哪个位置开始赠送？
        for i in range(n, 0, -1):
            # 当 i 为赠送时， 前面 哪个位置赠送的成本最低
            while q[-1][0] > i * 2 + 1:
                q.pop() # 后面 对 i 无影响的点 弹出
            f = prices[i - 1] + q[-1][1] # 后面确定要花的最少钱
            
            while f <= q[0][1]:
                q.popleft()
            q.appendleft((i, f))  # 左边进入窗口
        return q[0][1]

Explain

此题解采用了动态规划的思想，使用一个双端队列 (deque) 优化状态的转移过程。基本思路是从数组的末尾向前计算每个位置购买水果的最小花费。对于每个位置i，算法计算购买该水果并获取后续免费水果的总成本。双端队列用于存储可能的最小成本和对应的位置，从而快速获得后续位置的最小花费。队列中维护的是一系列（位置，花费）对，确保队列始终保持递增的花费顺序。如果当前计算的花费比队列头部的花费还低，那么头部的花费将不再有用，因此会被移除。每次计算都是基于队列中花费最小的位置来决定当前位置的最优决策。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        n = len(prices)
        q = deque([(n + 1, 0)])  # (index after last free fruit from current purchase, minimum cost from here)
        for i in range(n, 0, -1):
            # Maintain elements in deque that might influence current index i
            while q[-1][0] > i * 2 + 1:
                q.pop()  # Remove elements that won't affect the cost at index i
            f = prices[i - 1] + q[-1][1]  # Cost of buying at i and getting the minimum cost from the queue
            
            # Maintain deque as a monotonically increasing structure in terms of cost
            while f <= q[0][1]:
                q.popleft()
            q.appendleft((i, f))  # Add current cost and index
        return q[0][1]

Explore

在此动态规划解法中，每次购买水果都可能使得接下来的几个水果是免费的，具体到此题，购买位置i的水果时，可以免费获得位置i+1到2i的水果。因此，对于每个位置i，只需要考虑从i到2i位置之后的最小花费。队列`q`中存储的元组`(j, cost)`中，j代表最远可以免费到达的位置，cost是从该位置开始的最小花费。当`q[-1][0] > i * 2 + 1`时，意味着队列尾部的元素代表的状态超出了当前位置i免费范围的最远边界，因此不会影响到i位置的决策，可以被安全移除。

在计算当前位置i购买水果的总成本f时（包括购买i的花费和从i位置之后的最小花费），需要确保队列头部始终是可达范围内的最小花费。如果计算得出的新成本f小于等于队列头部的成本`q[0][1]`，这表明新计算的成本更优或等价，并且更靠前（即更早使用），因此原有的队列头部成本不再是最优选择，应该被移除。通过这种方式，我们确保队列头部始终保持最小花费，从而在后续的计算中可以直接使用。这个过程是必要的，以维持队列的状态正确反映从任何位置开始的最优花费。

为了保持队列花费递增的顺序，算法在添加新状态之前，会首先检查新计算的成本f是否小于等于队列头部的成本。如果是，算法会持续移除队列头部，直到队列头部的成本高于新成本f。这样做确保了只有最低的成本被保留在队列头部，而任何高于新成本的旧成本都被移除，保持了队列的成本递增。此外，每次对队尾的检查和移除操作也帮助维护了队列中的状态是当前和未来计算中可能用到的最优状态。