按递增顺序显示卡牌 图解题解

这道题到底在问什么

输入

deck=[2,3,5,8,13,21]（值的集合，摆放未知）

输出

[2,8,3,21,5,13]

最优解：一步一步想明白

1. 3记住这套「从大到小、先把队尾挪回队首撤销轮转、再把当前牌压入队首」，后面每一帧都在套它。
2. 4先看手里有哪些牌。输入顺序其实无所谓，因为题目允许我们任意重排，真正决定答案的只是这些值和张数。
3. 5把牌排好序，这一排就是我们希望被「依次亮出」的递增顺序。但注意：这不是牌堆的摆放，而是亮出的先后。难点正是把它倒推回摆放。
4. 6从最大的牌开始。队列还空着，直接把 21 放进去(绿色)。它是最后才会被亮出的牌，所以最先入列。
5. 7准备放入 13 之前，按套路要先把队尾挪回队首。可现在队列只有一张 21，挪过来还是它，走个流程即可，下一帧再压入 13。
6. 8把当前这张 13 压到队首(绿色)。它比已在队列里的都小，会比它们更早被亮出，所以排在更靠前的位置。
7. 9准备放入 8 之前，先撤销上一轮「把顶牌移到底部」：把队尾的 21 挪回队首(红色那张)。这一步保证倒放后队列能还原。
8. 10把当前这张 8 压到队首(绿色)。它比已在队列里的都小，会比它们更早被亮出，所以排在更靠前的位置。
9. 11准备放入 5 之前，先撤销上一轮「把顶牌移到底部」：把队尾的 13 挪回队首(红色那张)。这一步保证倒放后队列能还原。
10. 12把当前这张 5 压到队首(绿色)。它比已在队列里的都小，会比它们更早被亮出，所以排在更靠前的位置。
11. 13准备放入 3 之前，先撤销上一轮「把顶牌移到底部」：把队尾的 21 挪回队首(红色那张)。这一步保证倒放后队列能还原。
12. 14把当前这张 3 压到队首(绿色)。它比已在队列里的都小，会比它们更早被亮出，所以排在更靠前的位置。
13. 15准备放入 2 之前，先撤销上一轮「把顶牌移到底部」：把队尾的 8 挪回队首(红色那张)。这一步保证倒放后队列能还原。
14. 16把当前这张 2 压到队首(绿色)。它比已在队列里的都小，会比它们更早被亮出，所以排在更靠前的位置。
15. 17六张牌从大到小全部放完，队列从队首到队尾就是要求的牌堆摆放：[2, 8, 3, 21, 5, 13]。下面正着走一遍，验证它亮出来确实递增。
16. 18亮出当前牌堆顶部的 2(绿色)，记到「已亮出」里。到目前为止亮出的序列是 2，一直在变大。
17. 19按规则，把新的顶牌 8 移到牌堆底部(红色那张到了队尾)，轮到它后面的牌当顶。剩下的牌堆是 [3, 21, 5, 13, 8]。
18. 20亮出当前牌堆顶部的 3(绿色)，记到「已亮出」里。到目前为止亮出的序列是 2、3，一直在变大。
19. 21按规则，把新的顶牌 21 移到牌堆底部(红色那张到了队尾)，轮到它后面的牌当顶。剩下的牌堆是 [5, 13, 8, 21]。
20. 22亮出当前牌堆顶部的 5(绿色)，记到「已亮出」里。到目前为止亮出的序列是 2、3、5，一直在变大。
21. 23按规则，把新的顶牌 13 移到牌堆底部(红色那张到了队尾)，轮到它后面的牌当顶。剩下的牌堆是 [8, 21, 13]。
22. 24亮出当前牌堆顶部的 8(绿色)，记到「已亮出」里。到目前为止亮出的序列是 2、3、5、8，一直在变大。
23. 25按规则，把新的顶牌 21 移到牌堆底部(红色那张到了队尾)，轮到它后面的牌当顶。剩下的牌堆是 [13, 21]。
24. 26亮出当前牌堆顶部的 13(绿色)，记到「已亮出」里。到目前为止亮出的序列是 2、3、5、8、13，一直在变大。
25. 27按规则，把新的顶牌 21 移到牌堆底部(红色那张到了队尾)，轮到它后面的牌当顶。剩下的牌堆是 [21]。
26. 28亮出当前牌堆顶部的 21(绿色)，记到「已亮出」里。到目前为止亮出的序列是 2、3、5、8、13、21，一直在变大。
27. 29回放结束，亮出的顺序正好是 2、3、5、8、13、21，一路严格递增。这证明刚才逆向推出的摆放 [2, 8, 3, 21, 5, 13] 完全正确。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        q = deque()
        for v in sorted(deck, reverse=True):
            if q:
                q.appendleft(q.pop())
            q.appendleft(v)
        return list(q)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> deckRevealedIncreasing(vector<int>& deck) {
        sort(deck.rbegin(), deck.rend());
        deque<int> q;
        for (int v : deck) {
            if (!q.empty()) {
                q.push_front(q.back());
                q.pop_back();
            }
            q.push_front(v);
        }
        return vector<int>(q.begin(), q.end());
    }
};

import java.util.*;
class Solution {
    public int[] deckRevealedIncreasing(int[] deck) {
        Deque<Integer> q = new ArrayDeque<>();
        Arrays.sort(deck);
        int n = deck.length;
        for (int i = n - 1; i >= 0; --i) {
            if (!q.isEmpty()) {
                q.offerFirst(q.pollLast());
            }
            q.offerFirst(deck[i]);
        }
        int[] ans = new int[n];
        for (int i = n - 1; i >= 0; --i) {
            ans[i] = q.pollLast();
        }
        return ans;
    }
}

复杂度

面试官可能追问