maximize-the-topmost-element-after-k-moves

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

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

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

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

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

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

&nbsp;
Example 1:

<pre>
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.
</pre>

Example 2:

<pre>
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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i], k &lt;= 109</code></li>
</ul>

maximumTop

Maximize the Topmost Element After K Moves

Gas Station

gas-station

加油站

Greedy

Array

给你一个下标从 0&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;，它表示一个 堆 ，其中 <code>nums[0]</code>&nbsp;是堆顶的元素。

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

<ul>
	<li>如果堆非空，那么 删除&nbsp;堆顶端的元素。</li>
	<li>如果存在 1 个或者多个被删除的元素，你可以从它们中选择任何一个，添加&nbsp;回堆顶，这个元素成为新的堆顶元素。</li>
</ul>

同时给你一个整数&nbsp;<code>k</code>&nbsp;，它表示你总共需要执行操作的次数。

请你返回 恰好&nbsp;执行 <code>k</code>&nbsp;次操作以后，堆顶元素的 最大值&nbsp;。如果执行完 <code>k</code>&nbsp;次操作以后，堆一定为空，请你返回 <code>-1</code>&nbsp;。

&nbsp;

示例 1：

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

示例 2：

<pre>
输入：nums = [2], k = 1
输出：-1
解释：
第 1 次操作中，我们唯一的选择是将堆顶元素弹出堆。
由于 1 次操作后无法得到一个非空的堆，所以我们返回 -1 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= nums.length &lt;= 105</code></li>
	<li><code>0 &lt;= nums[i], k &lt;= 109</code></li>
</ul>