# 資訊

:::info
- Question: 950. Reveal Cards In Increasing Order
- From: Leetcode Daily Challenge 2024.04.10
- Difficulty: Medium
:::

---

# 目錄

:::info
[TOC]
:::

---

# 題目

You are given an integer array `deck`. There is a deck of cards where every card has a unique integer. The integer on the $i^{th}$ card is `deck[i]`.

You can order the deck in any order you want. Initially, all the cards start face down (unrevealed) in one deck.

You will do the following steps repeatedly until all cards are revealed:

1. Take the top card of the deck, reveal it, and take it out of the deck.
2. If there are still cards in the deck then put the next top card of the deck at the bottom of the deck.
3. If there are still unrevealed cards, go back to step 1. Otherwise, stop.

Return an ordering of the deck that would reveal the cards in increasing order.

Note that the first entry in the answer is considered to be the top of the deck.

> Example 1:
:::success
* Input: `deck = [17,13,11,2,3,5,7]`
* Output: `[2,13,3,11,5,17,7]`
* Explanation:
* We get the deck in the order `[17,13,11,2,3,5,7]` (this order does not matter), and reorder it.
* After reordering, the deck starts as `[2,13,3,11,5,17,7]`, where 2 is the top of the deck.
* We reveal 2, and move 13 to the bottom. The deck is now `[3,11,5,17,7,13]`.
* We reveal 3, and move 11 to the bottom. The deck is now `[5,17,7,13,11]`.
* We reveal 5, and move 17 to the bottom. The deck is now `[7,13,11,17]`.
* We reveal 7, and move 13 to the bottom. The deck is now `[11,17,13]`.
* We reveal 11, and move 17 to the bottom. The deck is now `[13,17]`.
* We reveal 13, and move 17 to the bottom. The deck is now `[17]`.
* We reveal 17.
* Since all the cards revealed are in increasing order, the answer is correct.
:::

> Example 2:
:::success
* Input: `deck = [1,1000]`
* Output: `[1,1000]`
:::

> Constraints:
:::success
* 1 <= `deck.length` <= 1000
* 1 <= `deck[i]` <= $10^6$
* All the values of `deck` are unique.
:::

---

# 解法

## 概念

這題是使用到 **deque**，Python 中的 deque 其實就是支援兩邊 append 和 pop 的好工具，以往的 append 只能從尾巴加上去，現在有 appendleft 可以用，而以往 pop 只能從尾巴 pop，現在有 popleft 可以用，底層實作應該是多幾支 pointer 穰我快速指過去而已，總之比較方便，耶！

今天就避免不了 simulation，仔細看題目說他會抽牌，然後把 top 移到 deck 下方，要直接使用 counting 把結果寫出來有點困難，而使用 simulation 也無從得知 deck 順序，唯一知道順序的是抽卡順序要由小到大，那就從這部分下手，而我要做的就是 "ex-simulation"，反模擬就可以了

原先題目是說「先抽卡再將 top 移到底部」，反模擬就把手牌當作另一個 deck，將手牌先蓋牌，然後再移動 buttom 至 top 就可以了

來看看程式碼：

第 3 - 4 行：創建手牌，也就是透過 deque，但因為等等要依序丟到 deck 中，所以 sorting 要 reverse 過
第 5 行：創建 deque
第 7 - 11 行：模擬放牌、移牌階段，注意要 append 到最左邊，也就是蓋到 deck 最上方
第 12 - 14 行：要把 deque 轉回 list，所以重新一個一個 append 上去 `ans`

## 程式碼

class Solution:
    def deckRevealedIncreasing(self, deck: List[int]) -> List[int]:
        # Sort `deck` from large to small
        deck.sort( reverse=True )
        dq = deque()
        n = len(deck)
        dq.appendleft(deck[0])
        for i in range(1,n):
            tmp = dq.pop()
            dq.appendleft(tmp)
            dq.appendleft(deck[i])
        ans = []
        while dq:
            ans.append(dq.popleft())
        return ans

---

# 複雜度

## 時間複雜度

複雜的時間主要在模擬那一段，但因為 deque 幫我把所有 append 和 pop 都用 $O(1)$ 時間做到，所以複雜度會是外層模擬的 $O(n)$


## 空間複雜度

空間複雜度會在 deque 身上，所以是 $O(n)$