2202. K 次操作后最大化顶端元素

题目描述

给你一个下标从 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 <= 10⁵
0 <= nums[i], k <= 10⁹

解法

方法一

思考

每次操作只能弹出栈顶或把先前弹出的某一元素放回顶部，\(k\) 可达 \(10^9\)，按步模拟不可行。需要把「恰好 \(k\) 次操作后的栈顶」收成几种可比较的情况。

\(k = 0\) 时栈顶即为 \(nums[0]\)。若数组只有一个元素，奇数次操作会把唯一元素弹出且无法放回，答案为 \(-1\)；偶数次则仍是该元素。

长度至少为 \(2\) 时，前 \(k-1\) 次弹出腾出的数都可以在第 \(k\) 次放回成为栈顶，故候选为 \(nums[0..k-2]\) 的最大值；若 \(k < n\)，也可以第 \(k\) 次继续弹出，使 \(nums[k]\) 暴露为栈顶。二者取较大值即可。

Python3JavaC++Go

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

class Solution {
    public int maximumTop(int[] nums, int k) {
        if (k == 0) {
            return nums[0];
        }
        int n = nums.length;
        if (n == 1) {
            if (k % 2 == 1) {
                return -1;
            }
            return nums[0];
        }
        int ans = -1;
        for (int i = 0; i < Math.min(k - 1, n); ++i) {
            ans = Math.max(ans, nums[i]);
        }
        if (k < n) {
            ans = Math.max(ans, nums[k]);
        }
        return ans;
    }
}

class Solution {
public:
    int maximumTop(vector<int>& nums, int k) {
        if (k == 0) return nums[0];
        int n = nums.size();
        if (n == 1) {
            if (k % 2) return -1;
            return nums[0];
        }
        int ans = -1;
        for (int i = 0; i < min(k - 1, n); ++i) ans = max(ans, nums[i]);
        if (k < n) ans = max(ans, nums[k]);
        return ans;
    }
};

func maximumTop(nums []int, k int) int {
    if k == 0 {
        return nums[0]
    }
    n := len(nums)
    if n == 1 {
        if k%2 == 1 {
            return -1
        }
        return nums[0]
    }
    ans := -1
    for i := 0; i < min(k-1, n); i++ {
        ans = max(ans, nums[i])
    }
    if k < n {
        ans = max(ans, nums[k])
    }
    return ans
}

2202. K 次操作后最大化顶端元素

题目描述

解法

方法一

评论