> 文档中心 > 我都懂了,你还能不懂?950. 按递增顺序显示卡牌——【详解+动图理解】

我都懂了,你还能不懂?950. 按递增顺序显示卡牌——【详解+动图理解】


前言

我理解能力这么差都懂了,你还能不懂?不懂锤我,这里我觉得应该写得挺详细的了。希望你有所收获!

950. 按递增顺序显示卡牌

题目

牌组中的每张卡牌都对应有一个唯一的整数。你可以按你想要的顺序对这套卡片进行排序。

最初,这些卡牌在牌组里是正面朝下的(即,未显示状态)。

现在,重复执行以下步骤,直到显示所有卡牌为止:

  1. 从牌组顶部抽一张牌,显示它,然后将其从牌组中移出。
  2. 如果牌组中仍有牌,则将下一张处于牌组顶部的牌放在牌组的底部。
  3. 如果仍有未显示的牌,那么返回步骤 1。否则,停止行动。

返回能以递增顺序显示卡牌的牌组顺序。

答案中的第一张牌被认为处于牌堆顶部。

示例:

输入:[17,13,11,2,3,5,7]输出:[2,13,3,11,5,17,7]解释:我们得到的牌组顺序为 [17,13,11,2,3,5,7](这个顺序不重要),然后将其重新排序。重新排序后,牌组以 [2,13,3,11,5,17,7] 开始,其中 2 位于牌组的顶部。我们显示 2,然后将 13 移到底部。牌组现在是 [3,11,5,17,7,13]。我们显示 3,并将 11 移到底部。牌组现在是 [5,17,7,13,11]。我们显示 5,然后将 17 移到底部。牌组现在是 [7,13,11,17]。我们显示 7,并将 13 移到底部。牌组现在是 [11,17,13]。我们显示 11,然后将 17 移到底部。牌组现在是 [13,17]。我们展示 13,然后将 17 移到底部。牌组现在是 [17]。我们显示 17。由于所有卡片都是按递增顺序排列显示的,所以答案是正确的。

思路

这道题一开始我读着是非常绕的,看了半天也没看懂,好在功夫不负有心人,看到 @杨枝 姐的题解,才焕然大悟。所以记录下来,我理解能力这么差都懂了,你还能不懂?

给我们的数组 [17,13,11,2,3,5,7] 顺序不重要,主要是需要我们得到一个排序后的数组能够实现题目所说的过程。示例中就是 [2,13,3,11,5,17,7] 这个数组,这个数组通过「显示顶部牌同时移除顶部牌,然后移动下一张牌到底部」的流程,进行的循环操作,直到没有牌,得到的显示序列就是最终的递增顺序排序的数组[2,3,5,7,11,13,17]。最终是递增有序的,那么我们可以从有序中入手,我们可以通过排序让数组变成递增有序。

通过上面知道

可以通过答案数组 [2,13,3,11,5,17,7] 经过上面所述的操作得到递增顺序排序的数组 [2,3,5,7,11,13,17]。

那我们可以反过来进行操作,把递增顺序排序的数组 [2,3,5,7,11,13,17],经过相反操作,变成答案数组 [2,13,3,11,5,17,7] 。

  • 它是「移除顶部牌,移到最后牌组里没有牌就结束」,那我们就「插入底部牌,插入到最后牌组里没有牌就结束」;

  • 它是「顶部牌移动到底部」,那我们就把「底部牌移动到顶部」,最后就能够还原成我们想要的答案数组了。

所以:题目给我们一个数组,我们只需要把它排序成有序的数组,然后进行反操作,最后牌组里没有牌可以插入了,那么就找到这个答案数组了。

我都懂了,你还能不懂?950. 按递增顺序显示卡牌——【详解+动图理解】

注:图中左边是牌组的顶部,右边是牌组的底部。上方是一开始排好序的牌组,每次拿一张牌来插入,然后底部的牌放到顶部,以此类推。(途中17和13是一起插入的,实际上并不是一起插入,只是画图省了,当然你可以想象,一开始就只有17,底部牌是17,顶部牌也是17,17搞定插入和移动后,下一个就是13插入了,所以这里就直接画成17和13一起放下来了)

代码

实现「底部插入到顶部」,可以使用双端队列这种数据结构,直接队尾出队,然后队头入队。

class Solution {    public int[] deckRevealedIncreasing(int[] deck) { int n = deck.length; Arrays.sort(deck); // [2,3,5,7,11,13,17] Deque<Integer> que = new LinkedList<>(); for (int i = n - 1; i >= 0; --i) {     que.addFirst(deck[i]); // 插入     if (i != 0) { // 最后以此不需要移了,不然多一次了,就会变成 [3,5,7,11,13,17,2]  que.addFirst(que.pollLast()); // 将底部的牌移到顶部     } } int j = 0; // 将双端队列中的值放到数组中返回 for (Integer val : que) {     deck[j++] = val; } return deck;    }}