LeetCode 题解工作台
K 次操作后最大化顶端元素
给你一个下标从 0 开始的整数数组 nums ，它表示一个 堆 ，其中 nums[0] 是堆顶的元素。 每一次操作中，你可以执行以下操作 之一 ： 如果堆非空，那么 删除 堆顶端的元素。 如果存在 1 个或者多个被删除的元素，你可以从它们中选择任何一个， 添加 回堆顶，这个元素成为新的堆顶元素。 同…
2
题型
4
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
class Solution: def maximumTop(self, nums: List[int], k: int) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个下标从 0 开始的整数数组 nums ，它表示一个 堆 ，其中 nums[0] 是堆顶的元素。
每一次操作中，你可以执行以下操作 之一 ：
- 如果堆非空，那么 删除 堆顶端的元素。
- 如果存在 1 个或者多个被删除的元素，你可以从它们中选择任何一个，添加 回堆顶，这个元素成为新的堆顶元素。
同时给你一个整数 k ，它表示你总共需要执行操作的次数。
请你返回 恰好 执行 k 次操作以后，堆顶元素的 最大值 。如果执行完 k 次操作以后，堆一定为空，请你返回 -1 。
示例 1：
输入：nums = [5,2,2,4,0,6], k = 4 输出：5 解释： 4 次操作后，堆顶元素为 5 的方法之一为： - 第 1 次操作：删除堆顶元素 5 ，堆变为 [2,2,4,0,6] 。 - 第 2 次操作：删除堆顶元素 2 ，堆变为 [2,4,0,6] 。 - 第 3 次操作：删除堆顶元素 2 ，堆变为 [4,0,6] 。 - 第 4 次操作：将 5 添加回堆顶，堆变为 [5,4,0,6] 。 注意，这不是最后堆顶元素为 5 的唯一方式。但可以证明，4 次操作以后 5 是能得到的最大堆顶元素。
示例 2：
输入：nums = [2], k = 1 输出：-1 解释： 第 1 次操作中，我们唯一的选择是将堆顶元素弹出堆。 由于 1 次操作后无法得到一个非空的堆，所以我们返回 -1 。
提示：
1 <= nums.length <= 1050 <= nums[i], k <= 109
解题思路
方法一
class Solution:
def maximumTop(self, nums: List[int], k: int) -> int:
if k == 0:
return nums[0]
n = len(nums)
if n == 1:
if k % 2:
return -1
return nums[0]
ans = max(nums[: k - 1], default=-1)
if k < n:
ans = max(ans, nums[k])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate identify the key greedy choice in this problem?
- question_mark
Does the candidate show an understanding of the invariant conditions required for the greedy approach?
- question_mark
Can the candidate handle edge cases, such as an empty pile or fewer than k elements?
常见陷阱
外企场景- error
Failing to recognize the greedy choice that maximizes the top element after exactly k moves.
- error
Incorrectly validating the invariant, leading to incorrect conclusions about the top element after k moves.
- error
Not handling edge cases properly, such as returning an incorrect result when the pile is emptied prematurely.
进阶变体
外企场景- arrow_right_alt
What if we were allowed to remove more than one element at a time?
- arrow_right_alt
How would the solution change if we could perform additional operations other than removing and adding elements?
- arrow_right_alt
How would you approach this problem if k were much larger than the number of elements in nums?