解題說明
Reveal Cards In Increasing Order
題目描述： 有一副牌，要求重新排列牌組，使得按照以下規則翻牌時，翻出的順序是遞增的：翻開最上面的牌，然後把下一張牌移到底部，重複此過程直到所有牌翻完。
解題思路：
- 模擬逆過程：先將牌排序。然後用一個佇列模擬翻牌的索引順序。
- 初始化佇列為 [0, 1, 2, ..., n-1]。
- 模擬翻牌過程：每次取出佇列前端的索引（這是第 i 張要翻的牌的位置），然後把下一個索引移到佇列末尾。
- 排序後的第 i 小的牌應該放在第 i 次取出的索引位置上。
- 這樣建構的牌組就能滿足翻牌順序為遞增。
C++ 解法
複雜度分析
時間複雜度：O(n log n) — 排序為瓶頸，佇列模擬為 O(n)
空間複雜度：O(n) — 佇列和結果陣列
虛擬碼
1. Sort deck in ascending order 2. Create a deque of indices [0, 1, 2, ..., n-1] 3. For i = 0 to n-1: a. Place deck[i] at position indices.front() in result b. Pop front index c. If deque not empty: move front to back (simulate the "move to bottom" step) 4. Return result
其他解法
-
逆向模擬：從最大的牌開始，反向模擬。維護一個雙端佇列存結果，每次從尾部移一張牌到頭部，然後把當前最大的牌放到頭部。最終佇列就是答案。直覺上更好理解「逆轉」過程。
-
遞迴分治：將問題拆成子問題。第一個位置放最小牌，然後遞迴處理剩餘位置（奇偶交替）。時間複雜度相同但實作較複雜。
延伸思考
- 如果翻牌規則改成「翻一張，移 k 張到底部」，答案如何變化？
- 如果不是要遞增而是要特定的翻牌順序呢？
- 如何驗證一個排列是否能產生遞增的翻牌順序？