数字游戏

难度: Hard

小扣在秋日市集入口处发现了一个数字游戏。主办方共有 `N` 个计数器，计数器编号为 `0 ~ N-1`。每个计数器上分别显示了一个数字，小扣按计数器编号升序将所显示的数字记于数组 `nums`。每个计数器上有两个按钮，分别可以实现将显示数字加一或减一。小扣每一次操作可以选择一个计数器，按下加一或减一按钮。主办方请小扣回答出一个长度为 `N` 的数组，第 `i` 个元素(0 <= i < N)表示将 `0~i` 号计数器 **初始** 所示数字操作成满足所有条件 `nums[a]+1 == nums[a+1],(0 <= a < i)` 的最小操作数。回答正确方可进入秋日市集。由于答案可能很大，请将每个最小操作数对 `1,000,000,007` 取余。 **示例 1：** >输入：`nums = [3,4,5,1,6,7]` > >输出：`[0,0,0,5,6,7]` > >解释： >i = 0，[3] 无需操作 >i = 1，[3,4] 无需操作； >i = 2，[3,4,5] 无需操作； >i = 3，将 [3,4,5,1] 操作成 [3,4,5,6], 最少 5 次操作； >i = 4，将 [3,4,5,1,6] 操作成 [3,4,5,6,7], 最少 6 次操作； >i = 5，将 [3,4,5,1,6,7] 操作成 [3,4,5,6,7,8]，最少 7 次操作； >返回 [0,0,0,5,6,7]。 **示例 2：** >输入：`nums = [1,2,3,4,5]` > >输出：`[0,0,0,0,0]` > >解释：对于任意计数器编号 i 都无需操作。 **示例 3：** >输入：`nums = [1,1,1,2,3,4]` > >输出：`[0,1,2,3,3,3]` > >解释： >i = 0，无需操作； >i = 1，将 [1,1] 操作成 [1,2] 或 [0,1] 最少 1 次操作； >i = 2，将 [1,1,1] 操作成 [1,2,3] 或 [0,1,2]，最少 2 次操作； >i = 3，将 [1,1,1,2] 操作成 [1,2,3,4] 或 [0,1,2,3]，最少 3 次操作； >i = 4，将 [1,1,1,2,3] 操作成 [-1,0,1,2,3]，最少 3 次操作； >i = 5，将 [1,1,1,2,3,4] 操作成 [-1,0,1,2,3,4]，最少 3 次操作； >返回 [0,1,2,3,3,3]。 **提示：** - `1 <= nums.length <= 10^5` - `1 <= nums[i] <= 10^3`

Submission

运行时间: 130 ms

内存: 35.3 MB

# https://leetcode.cn/u/l00/

class Solution:
    def numsGame(self, nums: List[int]) -> List[int]:
        MOD = 1_000_000_007
        ans = [0]

        nums = [i - num for i, num in enumerate(nums)]
        lower = higher = nums[0]
        for i, num in enumerate(nums[1:], 1):
            if lower > num: lower = num
            if higher < num: higher = num

        # 标准值左右两边的点位数量差值
        totalDiff = 0
        
        # 标准值，也就是当前最佳数值，得出最佳的结果的标准
        cur = nums[0] - lower
        cnt = [0] * (higher - lower + 1)
        cnt[cur] = 1
        
        # 一开始标准值必然就是第一个数，然后枚举后面全部情况
        res = 0
        for num in nums[1:]:
            diff = num - lower
            cnt[diff] += 1
            # 新值与标准值一致，不需要改变
            if diff == cur:
                ans.append(res)
                continue
            # 判断新值与标准值的大小，对比其添加方向上的数量是否超过另一个方向的数量
            # 如果超过，就进行移动，这样必然形成更优的结果
            if diff > cur:
                totalDiff -= 1
                res += diff - cur
                if totalDiff < -cnt[cur]:
                    target = cur + 1
                    while cnt[target] == 0: target += 1
                    totalDiff += cnt[cur]
                    res += (target - cur) * (totalDiff)
                    totalDiff += cnt[target]
                    cur = target

            else:
                totalDiff += 1
                res += cur - diff
                if totalDiff > cnt[cur]:
                    target = cur - 1
                    while cnt[target] == 0: target -= 1
                    totalDiff -= cnt[cur]
                    res += (target - cur) * (totalDiff)
                    totalDiff -= cnt[target]
                    cur = target

            res %= MOD
            ans.append(res)
        return ans

Explain

本题目的是通过最少的操作次数，使得数组nums的前i个元素满足nums[a]+1 == nums[a+1]的条件。为了方便处理，我们首先将数组nums中的每个元素减去其索引，得到一个新的数组。接着，我们从左到右遍历这个新数组，并维护一个当前的标准值cur，以及左右两边的元素数量差值totalDiff。每次遍历到一个新元素时，我们更新左右两边的元素数量，并根据这个数量差值来调整标准值cur，以及计算出当前的最少操作次数res，并将其加入到答案数组ans中。

时间复杂度: O(n)

空间复杂度: O(n)

# https://leetcode.cn/u/l00/

class Solution:
    def numsGame(self, nums: List[int]) -> List[int]:
        MOD = 1_000_000_007
        ans = [0]

        nums = [i - num for i, num in enumerate(nums)]
        lower = higher = nums[0]
        for i, num in enumerate(nums[1:], 1):
            if lower > num: lower = num
            if higher < num: higher = num

        # 标准值左右两边的点位数量差值
        totalDiff = 0
        
        # 标准值，也就是当前最佳数值，得出最佳的结果的标准
        cur = nums[0] - lower
        cnt = [0] * (higher - lower + 1)
        cnt[cur] = 1
        
        # 一开始标准值必然就是第一个数，然后枚举后面全部情况
        res = 0
        for num in nums[1:]:
            diff = num - lower
            cnt[diff] += 1
            # 新值与标准值一致，不需要改变
            if diff == cur:
                ans.append(res)
                continue
            # 判断新值与标准值的大小，对比其添加方向上的数量是否超过另一个方向的数量
            # 如果超过，就进行移动，这样必然形成更优的结果
            if diff > cur:
                totalDiff -= 1
                res += diff - cur
                if totalDiff < -cnt[cur]:
                    target = cur + 1
                    while cnt[target] == 0: target += 1
                    totalDiff += cnt[cur]
                    res += (target - cur) * (totalDiff)
                    totalDiff += cnt[target]
                    cur = target

            else:
                totalDiff += 1
                res += cur - diff
                if totalDiff > cnt[cur]:
                    target = cur - 1
                    while cnt[target] == 0: target -= 1
                    totalDiff -= cnt[cur]
                    res += (target - cur) * (totalDiff)
                    totalDiff -= cnt[target]
                    cur = target

            res %= MOD
            ans.append(res)
        return ans

Explore

在处理数组时，对每个元素减去其索引的操作是为了将问题转化为寻找一个连续的、以0开始递增的数列。原问题要求nums[a]+1 == nums[a+1]，减去索引后，这个条件变为新数组中的相邻元素应该相等。这种转换简化了问题，使得我们可以通过维护一个当前的标准值和左右两边的元素数量差值来优化操作，从而更有效地达到目标条件。

在算法中，`cur`表示当前的最优或标准值，即使得操作次数最小的目标数值。`totalDiff`是左右两边相对于`cur`的元素数量差值，用于判断是否需要调整`cur`以达到更优的操作次数。当新的元素数值与`cur`不一致时，根据它们的差值和`totalDiff`的正负，我们可以确定是增加还是减少`cur`，并计算因此产生的操作次数。调整`cur`时，我们还需要考虑跳过那些计数为0的值，以确保`cur`总是指向存在的元素，从而最小化操作次数。

当需要调整标准值`cur`到新的目标`target`，且`target`处的元素计数为0时，算法通过循环遍历`cnt`数组来寻找下一个非零计数的位置。这个遍历过程涉及向左或向右检查直到找到有元素的位置。通过这种方式，我们确保了`cur`总是更新到有效的、有实际元素存在的位置，即使需要跳过一些计数为0的间隔。这个过程是通过简单的循环实现的，保证了在调整`cur`时总能找到最近的有效目标值。