2969：购买水果需要的最少金币数 II（★★）

力扣第 2969 题

题目

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

给你一个 下标从 1 开始 的数组 prices，其中 prices[i] 表示你购买第 i 个水果所需的硬币数量。

水果市场有以下优惠活动：

• 如果你用 prices[i] 个硬币购买第 i 个水果， 那么接下来的 i 个水果你都可以免费获得。

请注意 即使你 可以 免费获得第 j 个水果，你仍然可以用 prices[j] 个硬币来购买它，以获取新的优惠。

返回 获得所有水果所需的 最小 硬币数量。

示例 1：

输入：prices = [3,1,2]
输出：4
解释：你可以按以下方式获取水果：
- 用3个硬币购买第1个水果，并且可以免费获得第2个水果。
- 用1个硬币购买第2个水果，并且可以免费获得第3个水果。
- 免费获得第三个水果。
请注意，即使你可以免费获得第2个水果，你还是购买了它，因为这是更优的选择。
可以证明4是获取所有水果所需的最小硬币数量。

示例 2：

输入：prices = [1,10,1,1]
输出：2
解释：你可以按以下方式获取水果：
- 用1个硬币购买第1个水果，并且可以免费获得第2个水果。
- 免费获得第2个水果。
- 用1个硬币购买第3个水果，并且可以免费获得第4个水果。
- 免费获得第4个水果。
可以证明2是获取所有水果所需的最小硬币数量。

提示：

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

分析

• 令 f[i] 代表购买第 i 个水果，能获得后面所有水果的最小硬币数
• 显然 f[i]=prices[i]+min(f[i+1:i*2+3])
• 区间最小值可以用单调队列维护，即可递推

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def minimumCoins(self, prices: List[int]) -> int:
        A = prices
        n = len(A)
        f = [inf]*n+[0]
        dq = deque([n])
        for i in range(n-1,0-1,-1):
            while i*2+2<dq[0]:
                dq.popleft()
            f[i] = A[i]+f[dq[0]]
            while dq and f[dq[-1]]>=f[i]:
                dq.pop()
            dq.append(i)
        return f[0]

175 ms