收集巧克力

标签: 数组 枚举

难度: Medium

给你一个长度为 n、下标从 0 开始的整数数组 nums，nums[i] 表示收集位于下标 i 处的巧克力成本。每个巧克力都对应一个不同的类型，最初，位于下标 i 的巧克力就对应第 i 个类型。

在一步操作中，你可以用成本 x 执行下述行为：

  • 同时修改所有巧克力的类型，将巧克力的类型 ith 修改为类型 ((i + 1) mod n)th。

假设你可以执行任意次操作，请返回收集所有类型巧克力所需的最小成本。

示例 1：

输入：nums = [20,1,15], x = 5
输出：13
解释：最开始，巧克力的类型分别是 [0,1,2] 。我们可以用成本 1 购买第 1 个类型的巧克力。
接着，我们用成本 5 执行一次操作，巧克力的类型变更为 [1,2,0] 。我们可以用成本 1 购买第 2 个类型的巧克力。
然后，我们用成本 5 执行一次操作，巧克力的类型变更为 [2,0,1] 。我们可以用成本 1 购买第 0 个类型的巧克力。
因此，收集所有类型的巧克力需要的总成本是 (1 + 5 + 1 + 5 + 1) = 13 。可以证明这是一种最优方案。

示例 2：

输入：nums = [1,2,3], x = 4
输出：6
解释：我们将会按最初的成本收集全部三个类型的巧克力，而不需执行任何操作。因此，收集所有类型的巧克力需要的总成本是 1 + 2 + 3 = 6 。

提示：

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 109
  • 1 <= x <= 109

Submission

运行时间: 73 ms

内存: 16.4 MB

class Solution:
    def minCost(self, nums: List[int], x: int) -> int:
        n = len(nums)
        arr = []
        dif = [0] * n
        idx = (nums.index(min(nums)) + n - 1) % n
        for _ in range(n):
            v = [nums[idx], idx, idx]
            while arr and arr[-1][0] > v[0]:
                u = arr.pop()
                v[2] = u[2]
                dif[(u[1] - idx + n) % n] -= u[0]
                dif[(u[2] - idx + n + 1) % n] += u[0]
            dif[1 % n] += v[0]
            dif[(v[2] - idx + n + 1) % n] -= v[0]
            arr.append(v)
            idx = (idx + n - 1) % n
        dif[1 % n], dif[0] = dif[1 % n] + x, 0
        return sum(nums) + min(accumulate(accumulate(dif)))

Explain

该题解运用了单调栈与差分数组的组合技术来寻找最小化收集所有类型巧克力的成本。首先，题解初始化了一个单调栈来存储三元组，每个三元组包含当前巧克力的成本、原始索引和栈中能够影响到的最远索引。接着，使用差分数组dif来跟踪成本变化，每次将最小的成本巧克力对应的成本加到差分数组中，并在必要时调整以保持栈的单调性。最后，通过两次累加差分数组来计算每种操作下的总成本，并找出最小成本。在这个过程中，算法通过从最小成本的巧克力开始，逐步调整和计算操作后的成本，以求得最优解。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minCost(self, nums: List[int], x: int) -> int:
        n = len(nums)
        arr = []  # 单调栈，用于维护可能的最小成本的巧克力
        dif = [0] * n  # 差分数组，用于计算成本变化
        idx = (nums.index(min(nums)) + n - 1) % n  # 从最小成本的巧克力开始
        for _ in range(n):
            v = [nums[idx], idx, idx]  # 当前考虑的巧克力的成本和索引
            # 维持栈的单调性，保证栈顶元素具有最小成本
            while arr and arr[-1][0] > v[0]:
                u = arr.pop()
                v[2] = u[2]
                dif[(u[1] - idx + n) % n] -= u[0]
                dif[(u[2] - idx + n + 1) % n] += u[0]
            dif[1 % n] += v[0]
            dif[(v[2] - idx + n + 1) % n] -= v[0]
            arr.append(v)
            idx = (idx + n - 1) % n
        dif[1 % n], dif[0] = dif[1 % n] + x, 0  # 考虑操作成本
        return sum(nums) + min(accumulate(accumulate(dif)))  # 计算最小总成本

Explore

在这个题解中，单调栈与差分数组组合技术被用于优化和简化对成本的计算。单调栈用于维护一个单调递增的成本序列，这样可以保证任何时候栈顶的巧克力都是具有最小成本的。这种结构帮助我们追踪成本最小的巧克力，并及时更新受这些成本影响的范围。差分数组则用于记录成本的增减变化。当我们在单调栈中添加或移除巧克力时，会在差分数组相应的位置记录成本的增加或减少，从而允许我们快速计算任何点的累积成本变化。最终通过累积差分数组来获取每种操作下的总成本，并从中找出最小值。

在单调栈的使用中，保持栈的单调性指的是栈内元素需要按照一定的顺序排列，这里是保持成本的单调递增。这种单调性的保持是为了确保任何时刻我们都能快速访问到当前成本最小的巧克力。当新的巧克力成本低于栈顶巧克力成本时，栈顶巧克力将不再有机会成为最小成本，因此需要被移出栈。这样可以避免不必要的重复计算和复杂的成本管理，同时简化了成本的更新和计算过程。

从最小成本的巧克力开始操作是基于成本最小化的策略。这样做可以确保我们在处理各种操作时，始终围绕成本最低的点进行优化。通过从最低成本开始，可以最大化利用巧克力的成本效益，因为这将是影响总成本的关键因素。此外，从成本最低点开始计算，使得我们的操作可以尽可能少地增加额外成本，从而在追求最小总成本的过程中保持效率和精确度。