Skip to content

Latest commit

 

History

History
 
 

2202.Maximize-the-Topmost-Element-After-K-Moves

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 

2202.Maximize-the-Topmost-Element-After-K-Moves

我们逐个元素考虑,对于第i个元素(以1-index记),它能否被K次操作之后排在队列的首位?

首先,我们为了将第i个元素放在首位,我们必须把前i-1个元素拿掉。这i-1次的remove操作是可以提前做而不影响最终结果的。注意,push的操作不能提前做,因为必须要先有removed的元素才能使得push操作有意义;反之,remove的操作不依赖于push,可以放心地提前。

将k自减i-1后,我们的目标元素就已经在队列首位了。此时假设我们还有k次操作要做,那么就分情况讨论。

  1. k==0,那么无需操作,现状就是期待的效果
  2. k==1,那么此时我们无论是remove还是push,都无法再让第i个元素出现在队列首位了。
  3. 如果k是偶数,那么显然,我们可以通过反复remove和push队首元素,使得第i个元素始终保持在队列首位。
  4. 如果k是奇数,其实也有办法。那就是先remove当前的两个元素、再push回第i个元素。然后再反复remove和push第i个元素,消耗偶数次的操作。注意,这个方法的前提是存在第i+1个元素。
  5. 类似于4有一种容易被忽略的想法。那就是先remove第i个元素,再依次push会第i-1个元素和第i个元素。然后再反复remove和push第i元素,消耗偶数次的操作。注意这个方法不需要存在第i+1个元素,但需要存在第i-1个元素。

以上几种情况能保证第i个元素能通过操作后被放置在队列首位。我们在所有符合条件的元素里找最大值即可。