北京住总第一开发建设有限公司网站小学学校网站建设计划

题目链接

Leetcode.2202 K 次操作后最大化顶端元素 Rating ： 1717

题目描述

给你一个下标从 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^5$
• $0<=nums[i],k<=10^9$

分析：

分类讨论：

• 当 nums.length == 1，
• • 当 k是奇数，此时栈中不会有元素，返回 -1。
• • 当 k是偶数，此时栈中就只有这个元素，返回 nums[0]。
• 当 nums.length > 1，
• • 最大栈顶元素为 max( max(nums[0],nums[1],nums[2],.....,nums[k-1]) , nums[k] )，即前 k-1个元素的最大值 和 第k+1个元素 这两者取一个最大值。

时间复杂度： $O(k)$

C++代码：

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

Java代码：

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