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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:32 2023-09-13 16:06:32 Updated    

给你一个下标从 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 <= 105
  • 0 <= nums[i], k <= 109

方法一：枚举

思路与算法

我们不妨假设栈中初始元素的数量为 n。由于在每次操作中，我们可以弹出元素（非空），或在 1 个或多个被弹出元素（如有）中任选一个重新添加回栈顶，我们可以对 n 的大小分类讨论：

  • n = 1，此时，我们每一步的操作是确定的，即奇数次操作将唯一的元素弹出栈，偶数次再加回。那么，当 k 为偶数时，栈顶元素的最大值即为栈中唯一元素的数值，即 nums}[0]，我们返回该值作为答案；而当 k 为奇数时，操作完栈为空，此时应返回 -1。

  • n > 1，此时由操作方式不确定，因此枚举操作方式是不现实的，不过我们依旧可以分类讨论来枚举最终的栈顶元素。此时根据操作的类型又可以分为两种情况讨论：

    • 每次操作均弹出元素（此时要求 n \ge k），最终当取等号时栈为空，取大于号时，栈顶为 nums}[k]。
    • 至少有一次添加操作，亦即至多 k - 1 次弹出操作。由于越晚添加，理论可选的元素越多，因此我们不妨假设最后一次为添加操作。此时，下标位于 [0, min(n - 1, k - 2)] 闭区间的元素都可以作为最终的栈顶元素在最后一次操作时被添加进栈。

    综上，这种情况下，在 [0, k] 闭区间内除了 k - 1 以外的所有合法下标都可以成为栈顶的元素。此时我们只需要计算这些元素的最大值并返回即可。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maximumTop(vector<int>& nums, int k) {
        int n = nums.size();
        int res = -1;   // 最大的栈顶元素
        if (n == 1) {
            // n = 1 时若 k 为奇数则栈最终为空，此时返回 -1
            if (k % 2 == 0) {
                res = nums[0];
            }
        } else {
            for (int i = 0; i < min(n, k + 1); ++i) {
                if (i != k - 1) {
                    res = max(res, nums[i]);
                }
            }
        }
        return res;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maximumTop(self, nums: List[int], k: int) -> int:
        n = len(nums)
        res = -1   # 最大的栈顶元素
        if n == 1:
            # n = 1 时若 k 为奇数则栈最终为空，此时返回 -1
            if k % 2 == 0:
                return nums[0]
        else:
            for i in range(min(n, k + 1)):
                if i != k - 1:
                    res = max(res, nums[i])
        return res

复杂度分析

  • 时间复杂度：O(n)，其中 n 为数组 nums 的长度。即为枚举所有可能的栈顶元素并计算最大值的时间复杂度。

  • 空间复杂度：O(1)。

 Comments
On this page
2202-K 次操作后最大化顶端元素