k次操作后最大化顶端元素

1 引言

本题来源于力扣284周竞赛的第三题，在做周竞赛时，我未做出这道题，这是我看过题解之后写出来的。

2 问题

给你一个下标从 0 开始的整数数组 nums ，它表示一个 栈 ，其中 nums[0] 是栈顶的元素。每一次操作中，你可以执行以下操作 之一 ：

如果栈非空，那么 删除 栈顶端的元素。

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

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

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

示例:

输入：nums = [5,2,2,4,0,6], k = 4

输出：5

3 方法

本题最重要的是要考虑到那些特殊的值，如：k == 0, k == 1, n == 1 (n == len(nums))。

在k == 0时，不对数组nums进行操作，直接返回nums[0]。

在k == 1时，考虑n的值，n > 1时，返回nums[1]。否则返回-1。

在n == 1时，考虑k的奇偶，如果k为奇数，返回-1。否则返回nums[0]。

除此之外，都是一般情况:

一般情况又分俩种：

（1）k < n:比较nums[:k - 1]内的最大值与nums[k]的大小，返回最大的值。

（2）k >= n:直接返回nums[:k - 1]的最大值。

4 实验结果与讨论

通过实验、实践等证明提出的方法是有效的，是能够解决开头提出的问题。

代码清单

class Solution:

    def maximumTop(self, nums: List[int], k: int) -> int:

        n = len(nums)

        if k == 0:

            return nums[0]

        if n == 1:

            if k % 2 == 0:

                return max(nums)

            else:

                return -1

        if k == 1:

            return nums[1]

        a = max(nums[: k - 1])

        if k < n:

            b = nums[k]

            return max(a, b)

        return a

5 总结

在做这道题时一定要考虑到这些特殊的值并把它考虑完全，我一开始就是因为没有将这些特殊值考虑完全才错误百出的。

稿件来源：深度学习与文旅应用实验室（DLETA）

作者：王雷

实习编辑：衡辉