LCP24.数字游戏

链接：LCP24.数字游戏
难度：Hard
标签：数组、数学、堆（优先队列）
简介：主办方请小扣回答出一个长度为 N 的数组，第 i 个元素(0 <= i < N)表示将 0~i 号计数器 初始 所示数字操作成满足所有条件 nums[a]+1 == nums[a+1],(0 <= a < i) 的最小操作数。

题解 1 - python

• 编辑时间：2024-02-01
• 执行用时：248ms
• 内存消耗：34.91MB
• 编程语言：python
• 解法介绍：依次递增转换为使每个数都保持一致的最小步数。

class Solution:
    def numsGame(self, nums: List[int]) -> List[int]:
        lq = []
        rq = []
        res = []
        rsum = lsum = 0
        mod = 10 ** 9 + 7
        for i in range(len(nums)):
            num = nums[i] - i
            if lq and -lq[0] >= num:
                lsum += num
                heappush(lq, -num)
            else:
                rsum += num
                heappush(rq, num)
            # print(f'lq = {lq}, lsum = {lsum}')
            # print(f'rq = {rq}, rsum = {rsum}')
            if len(lq) > len(rq):
                num = -heappop(lq)
                lsum -= num
                rsum += num
                heappush(rq, num)            
            elif len(lq) < len(rq) - 1:
                num = heappop(rq)
                lsum += num
                rsum -= num
                heappush(lq, -num)
            # print(f'lq = {lq}, lsum = {lsum}')
            # print(f'rq = {rq}, rsum = {rsum}')
            if (i + 1) % 2 == 0:
                res.append((rsum - lsum) % mod)
            else:
                res.append((rsum - lsum - rq[0]) % mod)
        return res