难度: Hard
Submission
运行时间: 30 ms
内存: 16.1 MB
class Solution:
def convertArray(self, nums: List[int]) -> int:
def helper(nums):
res, pq = 0, []
for num in nums:
if not pq:
heappush(pq, - num)
else:
premax = -pq[0]
if premax > num:
res += premax - num
heappop(pq)
heappush(pq, -num)
heappush(pq, -num)
return res
return min(helper(nums), helper(nums[::-1]))
Explain
这道题的思路是使用贪心算法和优先队列（堆）。首先定义一个辅助函数 helper，它负责计算将数组变为单调递增所需的最小操作次数。遍历数组中的每个元素，对于每个元素，如果优先队列为空，则将其加入队列。如果队列不为空，则检查队列中的最大元素（队列是最大堆）是否大于当前元素，如果是，则将最大元素替换为当前元素，并将差值累加到结果中。这样做的目的是为了保持数组的单调递增性，同时减少操作次数。最后，返回将数组变为单调递增和单调递减的最小操作次数中的较小值。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def convertArray(self, nums: List[int]) -> int:
def helper(nums):
res, pq = 0, []
for num in nums:
if not pq:
heappush(pq, - num)
else:
premax = -pq[0]
if premax > num:
res += premax - num
heappop(pq)
heappush(pq, -num)
heappush(pq, -num)
return res
return min(helper(nums), helper(nums[::-1]))
Explore
题解中分别计算数组变为单调递增和单调递减的操作次数是为了找到将数组变为有序（无论是递增还是递减）的最小操作次数。因为题目的目标是使数组有序，而不仅仅是单调递增。有些情况下，使数组变为单调递减的操作次数可能比使其变为单调递增更少。例如，在一个主要递减的数组中，继续使其递减可能需要更少的修改。因此，计算两种情况并取最小值是确保找到最优解的关键。
在`helper`函数中，如果前一个最大元素大于当前元素，替换最大元素的主要目的是为了减少后续的潜在操作次数，从而使得整个数组更容易变成单调递增。通过替换最大元素为当前较小元素，我们可以减少该位置所需的调整量，并减少对后续元素的影响。若保留较大的元素，可能会导致后续更多的替换需要发生，从而增加总体的操作次数。
在Python中，标准库的堆实现（heapq）是一个最小堆。为了使用这一数据结构实现最大堆的效果，我们通过取负数的方式将最大元素转换为最小元素。这样，原本最大的元素在取负后变为最小，适合最小堆的操作。当从堆中取出元素时，再次取负即可恢复原来的值。这是一种常见的技巧，用以在只有最小堆实现的环境中实现最大堆的功能。
最大元素被替换后，再次将当前元素加入堆中是为了维护堆的结构和大小。在算法中，每次比较都基于堆顶（最大元素）进行，如果仅是替换而不重新加入当前元素，会导致堆中元素数量减少，从而影响后续操作的正确性。重新加入当前元素保证了每个原始数组元素都得到考虑，同时维持了堆的大小和结构，保证了算法的逻辑一致性和正确性。