[LeetCode] 2202. Maximize the Topmost Element After K Moves

You are given a 0-indexed integer array nums representing the contents of a pile, where nums[0] is the topmost element of the pile.

In one move, you can perform either of the following:

• If the pile is not empty, remove the topmost element of the pile.
• If there are one or more removed elements, add any one of them back onto the pile. This element becomes the new topmost element.

You are also given an integer k, which denotes the total number of moves to be made.

Return the maximum value of the topmost element of the pile possible after exactly k moves. In case it is not possible to obtain a non-empty pile after k moves, return -1.

Example 1:

Input: nums = [5,2,2,4,0,6], k = 4
Output: 5
Explanation:
One of the ways we can end with 5 at the top of the pile after 4 moves is as follows:
- Step 1: Remove the topmost element = 5. The pile becomes [2,2,4,0,6].
- Step 2: Remove the topmost element = 2. The pile becomes [2,4,0,6].
- Step 3: Remove the topmost element = 2. The pile becomes [4,0,6].
- Step 4: Add 5 back onto the pile. The pile becomes [5,4,0,6].
Note that this is not the only way to end with 5 at the top of the pile. It can be shown that 5 is the largest answer possible after 4 moves.

Example 2:

Input: nums = [2], k = 1
Output: -1
Explanation: 
In the first move, our only option is to pop the topmost element of the pile.
Since it is not possible to obtain a non-empty pile after one move, we return -1.

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i], k <= 109

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

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

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

如果栈非空，那么 删除 栈顶端的元素。
如果存在 1 个或者多个被删除的元素，你可以从它们中选择任何一个，添加 回栈顶，这个元素成为新的栈顶元素。
同时给你一个整数 k ，它表示你总共需要执行操作的次数。

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximize-the-topmost-element-after-k-moves
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是贪心。因为题目允许你做 K 次操作，假设数组长度足够长，理论上有两种情况

• 最大的元素在拿出来的前 K - 1 个元素里，最后一步操作把最大值放回栈顶。如果是这种情况，我们就记录一下前 K - 1 个元素里最大的那个返回即可
• 最大的元素在下标为 K 的位置上（其实他是第 K + 1 个元素），我们要做的就是拿走前面 K 个元素。如果是这种情况，我们不光要记录一下前 K 个元素里最大的那个，同时还需要跟下标为 K + 1 的那个元素比较一下，看谁更大

还有一个 corner case 是如果 K 是奇数且数组长度 == 1，只能返回 -1，因为这唯一的一次操作只能去弹出元素。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int maximumTop(int[] nums, int k) {
 3         int len = nums.length;
 4         // corner case
 5         if (k % 2 == 1 && len == 1) {
 6             return -1;
 7         }
 8 
 9         // normal case
10         int max = 0;
11         for (int i = 0; i < Math.min(k - 1, len); i++) {
12             max = Math.max(max, nums[i]);
13         }
14         return Math.max(max, k < len ? nums[k] : 0);
15     }
16 }

LeetCode 题目总结