力扣第 284 场周赛 ：K 次操作后最大顶端元素

一、问题描述

给你一个下标从 0 开始的整数数组 nums ，它表示一个 栈 ，其中 nums[0] 是栈顶的元素。

每一次操作中，你可以执行以下操作 之一 ：

• 如果栈非空，那么 删除 栈顶端的元素。
• 如果存在 1 个或者多个被删除的元素，你可以从它们中选择任何一个，添加 回栈顶，这个元素成为新的栈顶元素。

同时给你一个整数 k ，它表示你总共需要执行操作的次数。

请你返回 恰好 执行 k 次操作以后，栈顶元素的 最大值 。如果执行完 k 次操作以后，栈一定为空，请你返回 -1 。

题目链接：K 次操作后最大顶端元素

二、题目要求

样例

输入：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是能得到的最大栈顶元素。

考察

贪心模拟
建议用时15~35min

三、问题分析

这一题要试着去理解，最大的顶端元素你事先是不知道在哪的，并且也不确定K次操作能否达到。

正如《阿甘正传》所说：“人生就像一盒巧克力，你永远不知道下一块是什么味道。”

这题我们要试着在允许的操作步数内，寻找到最大的元素。为了增加成功的概率，删除栈顶元素个数要尽可能多，逐步向后遍历。而在遍历的过程中也不能忽略，定义m保存删除元素中最大的，留着后续比较。

K次操作，那我们K-1次进行删除，遍历尽可能多的元素。

最后一次操作时，有两种选择：一种是选取之前删除的最大元素，另一种是在删除一个元素取栈顶元素。

两种比较一下，谁最大就行。

特殊情况：

当元素个数只有一个时，如果操作数为奇数，那么无法输出元素，只能输出-1。
假如操作数大于元素个数，那么只需要完全遍历数组寻找最大值就行

四、编码实现

classSolution {
public:
intmaximumTop(vector<int>&nums, intk) {
inti,n=nums.size(),m=0;//初始化操作if(n==1&&k%2==1)//特殊情况，返回-1return-1;
for(i=0;i<k-1&&i<n;i++)//k-1次删除操作        {
m=max(m,nums[i]);
        }
if(k<n)//最后一次选择操作m=max(m,nums[k]);//输出结果returnm;  
    }
};

五、测试结果