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

难度: Medium

给你一个下标从 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⁹

Submission

运行时间: 36 ms

内存: 29.6 MB

class Solution:
    def maximumTop(self, nums: List[int], k: int) -> int:
        if len(nums)==1:
            if k%2==1:
                return -1
            else:
                return nums[0]
        if k==0:
            return nums[0]
        if k==1:
            return nums[1]
        else:
            if k>len(nums):
                return max(nums)
            a=max(nums[:k-1])
            if k==len(nums):
                return a
            return max(a,nums[k])

Explain

此题解是通过分析不同操作次数k和数组长度的关系，选择不同的策略来找出最大的栈顶元素。首先，如果数组只包含一个元素，则当k为奇数时，操作后栈一定为空（因为每次添加元素需要先有删除动作），返回-1；k为偶数时，可以通过删除和添加同一个元素来维持栈不变，返回该元素。如果k为0，直接返回栈顶元素。如果k为1，返回第二个元素，因为栈顶元素已被删除。对于更多操作次数，如果k大于数组长度，返回数组中的最大值，因为可以完全清空栈后随意添加。如果k等于数组长度，返回前k-1个元素的最大值，因为最后一次操作不能是添加操作（没有更多元素可以删除）。否则，比较前k-1个元素的最大值和第k个元素，返回两者中的最大值，因为最后一步操作可能是添加第k个元素。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def maximumTop(self, nums: List[int], k: int) -> int:
        if len(nums) == 1:
            # 如果数组只有一个元素，根据k是奇数还是偶数决定返回值
            if k % 2 == 1:
                return -1
            else:
                return nums[0]
        if k == 0:
            # 如果不需要任何操作，直接返回栈顶元素
            return nums[0]
        if k == 1:
            # 如果只需要一次操作，返回新的栈顶元素，即原来的第二个元素
            return nums[1]
        else:
            # 当k大于数组长度时，返回数组中的最大值
            if k > len(nums):
                return max(nums)
            # 取前k-1个元素中的最大值
            a = max(nums[:k-1])
            if k == len(nums):
                # 如果k等于数组长度，最后一个操作不能是添加操作
                return a
            # 返回前k-1个元素的最大值和第k个元素的较大值
            return max(a, nums[k])

Explore

当数组只包含一个元素且k为奇数时，返回-1的逻辑依据是每次操作都需要先删除一个元素再添加一个元素。由于k为奇数，进行的操作次数是奇数次，因此最后一次操作是删除操作，导致栈为空。在这种情况下，栈顶元素不存在，因此无法再添加任何元素，最终结果为栈空，返回-1。

当k大于数组长度时，可以先使用若干操作完全清空栈（使用数组长度次删除操作），此时还剩余k - 数组长度次操作可以进行。由于栈已空，剩余的操作将仅包括添加操作。在这种情况下，我们可以选择数组中的任何一个元素添加到空栈中，因此返回数组中的最大值是确保最终栈顶元素尽可能大的最佳策略。这种策略的有效性在于它允许我们在任意选择元素进行添加，从而最大化栈顶元素的值。

当k等于数组长度时，根据题解策略，可以先执行k次删除操作来清空栈。此时，由于栈已经为空且没有其他元素可以删除，无法进行更多的删除操作。由于栈中已无元素，最后一个操作不能是再次添加操作，因为该操作应来自栈中已删除的元素。因此，最后一个操作只能是删除操作，导致栈为空。

题解确实提到当k为1时，应返回第二个元素作为解。然而，这种情况没有考虑到数组长度可能小于2的特殊情况。如果数组只有一个元素，根据题解中之前的逻辑，进行一次操作意味着删除这个唯一的元素，导致栈为空。因此，在数组只有一个元素的情况下，如果k为1，应返回-1，表示栈顶元素不存在。