3264. K 次乘运算后的最终数组状态

🎯 问题描述

描述：
给你一个整数数组 nums，一个整数 k 和一个整数 multiplier。
你需要对 nums 执行 k 次操作，每次操作中：

找到 nums 中的 最小值 x。如果有多个最小值，选择 下标最小 的那个。
将该最小值替换为 x * multiplier。

请你返回执行完 k 次操作后，最终的 nums 数组。

说明：

这是一个典型的**堆（优先队列）**应用问题。
核心策略：
- 题目要求每次都要找到“最小”且“下标最小”的元素，这正是最小堆最擅长的操作。
- 由于 Python 的 heapq 模块默认提供最小堆，我们可以直接将元素存入堆中。
- 为了满足“数值相同取下标最小”的条件，我们将 (数值, 下标) 作为一个元组存入堆中。Python 在比较元组时，会优先比较第一个元素，如果相同再比较第二个元素，完美契合题目要求。
- 每次从堆顶取出最小元素，乘以 multiplier 后再放回堆中，重复 k 次即可。
示例：
示例 1：

输入：nums = [2,1,3,5,6], k = 5, multiplier = 2
输出：[8,4,6,5,6]
解释：
操作 1：最小值为 1 (下标 1)，变为 1*2=2，数组变为 [2,2,3,5,6]
操作 2：最小值为 2 (下标 0)，变为 2*2=4，数组变为 [4,2,3,5,6]
操作 3：最小值为 2 (下标 1)，变为 2*2=4，数组变为 [4,4,3,5,6]
操作 4：最小值为 3 (下标 2)，变为 3*2=6，数组变为 [4,4,6,5,6]
操作 5：最小值为 4 (下标 0)，变为 4*2=8，数组变为 [8,4,6,5,6]

💻 解题思路

思路1：最小堆（优先队列）模拟

核心逻辑

构建最小堆：
- 遍历 nums 数组，将每个元素的 (数值, 原始下标) 作为一个元组存入列表。
- 使用 heapq.heapify() 将列表原地转换为最小堆。
模拟 k 次操作：
- 循环 k 次，每次从堆顶弹出最小的元组 (val, idx)。
- 将 val 乘以 multiplier，得到新值。
- 将新值与原始下标组成的元组 (val * multiplier, idx) 重新压入堆中。
还原最终数组：
- 操作结束后，堆中包含了所有元素的最终状态，但顺序是堆序而非原始顺序。
- 创建一个长度为 n 的结果数组 res。
- 遍历堆中的所有元组，根据元组中的 idx 将最终的 val 填入 res 的对应位置。

代码实现

import heapq
from typing import List

class Solution:
    def getFinalState(self, nums: List[int], k: int, multiplier: int) -> List[int]:
        n = len(nums)
        # 1. 构建最小堆，存入 (数值, 原始下标) 的元组
        # Python 比较元组时，会先比第一个元素，再比第二个，完美满足题目要求
        heap = [(nums[i], i) for i in range(n)]
        heapq.heapify(heap)
        
        # 2. 模拟 k 次乘运算操作
        for _ in range(k):
            val, idx = heapq.heappop(heap)  # 弹出当前最小且下标最小的元素
            heapq.heappush(heap, (val * multiplier, idx))  # 乘完后放回堆中
        
        # 3. 根据原始下标还原最终的数组顺序
        res = [0] * n
        for val, idx in heap:
            res[idx] = val
            
        return res

📊 性能分析

时间复杂度：O((n + k) log n)
- 构建初始堆的时间复杂度为 O(n)。
- 每次 heappop 和 heappush 操作的时间复杂度为 O(log n)。
- 我们一共进行 k 次操作，因此总时间复杂度为 O((n + k) log n)。
空间复杂度：O(n)
- 需要一个堆来存储 n 个元素的元组，以及一个结果数组。

思考

为什么要存 (数值, 下标) 元组？
- 题目有一个关键约束：“如果有多个最小值，选择下标最小的那个”。
- 如果只存数值，当数值相同时，堆无法区分哪个下标更小。
- 利用 Python 元组的比较规则（先比第一个元素，相等则比第二个），将 (数值, 下标) 存入堆中，可以自动保证在数值相同时，下标小的元组会排在堆顶。
为什么最后需要还原数组？
- 堆是一个完全二叉树结构，它只保证堆顶是最小值，堆内的其他元素并不是按顺序排列的。
- 因此，操作结束后，堆中元素的顺序并不是原始数组的顺序。我们需要利用存入的 idx（原始下标）将最终的计算结果填回正确的位置。
数据范围的考量：
- 在实际的编程中，如果 k 很大且 multiplier 很大，val * multiplier 可能会导致整数溢出。不过在 Python 中，整数可以无限大，不需要担心溢出问题。但在 C++ 或 Java 等语言中，可能需要使用 long long 类型。
与其他解法的对比：
- 如果使用暴力法，每次操作都遍历数组找最小值，时间复杂度为 O(k * n)。当 k 和 n 较大时，效率会远低于堆解法。