Medium

题目描述

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

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

  • 如果栈不为空，删除栈顶元素。
  • 如果有一个或者多个被删除的元素，将其中任何一个添加回栈顶。

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

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

示例 1：

输入：nums = [5,2,2,4,0,6], k = 4
输出：5
解释：
一种可以得到栈顶元素为 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 <= nums.length <= 10^5
  • 0 <= nums[i], k <= 10^9

解题思路

这是一道贪心策略题，需要分析不同情况下的最优操作。

核心思路：

  1. 特殊情况处理：如果数组只有一个元素且 k 为奇数，则最终栈为空，返回 -1。
  2. 可达元素分析：通过 k 次操作，我们可以让某个元素成为栈顶，需要分析哪些位置的元素是可达的。
  3. 贪心选择：在所有可达的元素中选择最大值。

关键观察：

  • 要让位置 i 的元素成为栈顶，需要先移除前 i 个元素（i 步），然后放回该元素（1 步），总共需要 i+1 步。
  • 如果 k > i+1，剩余的步数必须是偶数，这样才能保持该元素在栈顶。
  • 当 k >= nums.length 时，如果剩余步数为偶数，可以选择前 nums.length-1 个元素中的最大值；如果为奇数，选择前 nums.length 个元素中的最大值。

算法步骤：

  1. 处理特殊情况：n=1 且 k 为奇数
  2. 如果 k >= n，根据 (k-n) 的奇偶性选择不同范围的最大值
  3. 否则，在前 k 个元素和位置 k 的元素中选择最大值

代码实现

class Solution {
public:
    int maximumTop(vector<int>& nums, int k) {
        int n = nums.size();
        
        // 特殊情况：只有一个元素且k为奇数
        if (n == 1 && k % 2 == 1) {
            return -1;
        }
        
        // 如果k >= n，可以访问所有元素
        if (k >= n) {
            if ((k - n) % 2 == 0) {
                // 剩余步数为偶数，可以选择前n-1个元素的最大值
                if (n == 1) return nums[0];
                return *max_element(nums.begin(), nums.end() - 1);
            } else {
                // 剩余步数为奇数，可以选择所有元素的最大值
                return *max_element(nums.begin(), nums.end());
            }
        }
        
        // k < n的情况
        int result = -1;
        
        // 考虑前k个元素中的最大值（可以移除后再放回）
        if (k > 0) {
            for (int i = 0; i < min(k, n); i++) {
                result = max(result, nums[i]);
            }
        }
        
        // 考虑位置k的元素（移除k个元素后露出的元素）
        if (k < n) {
            result = max(result, nums[k]);
        }
        
        return result;
    }
};

class Solution:
    def maximumTop(self, nums: List[int], k: int) -> int:
        n = len(nums)
        
        # 特殊情况：只有一个元素且k为奇数
        if n == 1 and k % 2 == 1:
            return -1
        
        # 如果k >= n，可以访问所有元素
        if k >= n:
            if (k - n) % 2 == 0:
                # 剩余步数为偶数，可以选择前n-1个元素的最大值
                if n == 1:
                    return nums[0]
                return max(nums[:-1])
            else:
                # 剩余步数为奇数，可以选择所有元素的最大值
                return max(nums)
        
        # k < n的情况
        result = -1
        
        # 考虑前k个元素中的最大值（可以移除后再放回）
        if k > 0:
            result = max(nums[:k])
        
        # 考虑位置k的元素（移除k个元素后露出的元素）
        if k < n:
            result = max(result, nums[k])
        
        return result

public class Solution {
    public int MaximumTop(int[] nums, int k) {
        int n = nums.Length;
        
        // 特殊情况：只有一个元素且k为奇数
        if (n == 1 && k % 2 == 1) {
            return -1;
        }
        
        // 如果k >= n，可以访问所有元素
        if (k >= n) {
            if ((k - n) % 2 == 0) {
                // 剩余步数为偶数，可以选择前n-1个元素的最大值
                if (n == 1) return nums[0];
                return nums.Take(n - 1).Max();
            } else {
                // 剩余步数为奇数，可以选择所有元素的最大值
                return nums.Max();
            }
        }
        
        // k < n的情况
        int result = -1;
        
        // 考虑前k个元素中的最大值（可以移除后再放回）
        if (k > 0) {
            result = nums.Take(k).Max();
        }
        
        // 考虑位置k的元素（移除k个元素后露出的元素）
        if (k < n) {
            result = Math.Max(result, nums[k]);
        }
        
        return result;
    }
}

var maximumTop = function(nums, k) {
    const n = nums.length;
    
    if (n === 1) {
        return k % 2 === 0 ? nums[0] : -1;
    }
    
    if (k === 1) {
        return n > 1 ? nums[1] : -1;
    }
    
    if (k > n) {
        return Math.max(...nums);
    }
    
    let maxVal = -1;
    
    for (let i = 0; i < Math.min(k - 1, n); i++) {
        maxVal = Math.max(maxVal, nums[i]);
    }
    
    if (k < n) {
        maxVal = Math.max(maxVal, nums[k]);
    }
    
    return maxVal;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度时间复杂度空间复杂度
最优解法O(n)O(1)

说明：

  • 时间复杂度：需要遍历数组找到最大值，最坏情况下需要 O(n) 时间
  • 空间复杂度：只使用常数额外空间

相关题目