主題
題目連結：
題目意譯：
你被給定一字串 s 而現在有一個機器人正擁有一個空字串 t。一直執行以下操作直到 s 和 t 都是空字串：
從 s 中移除第一個字元並交給機器人。機器人將會把該字元放到字串 t 的結尾。
從 t 中移除最後一個字元並交給機器人。機器人將會把該字元寫在紙上。
回傳可以寫在紙上的最小字典序字串。
限制：
1 ≦ s.length ≦ 10 ^ 5
s 只由小寫英文字母組成。
範例測資：
範例 1：
輸入： s = "zza"
輸出： "azz"
解釋： 令 p 代表著寫在紙上的字串。
一開始 p = "" 、 s = "zza" 、 t = ""。
執行第一個操作三次，p = "" 、 s = "" 、 t = "zza"。
執行第二個操作三次，p = "azz" 、 s = "" 、 t = ""。
範例 2：
輸入： s = "bac"
輸出： "abc"
解釋： 令 p 代表著寫在紙上的字串。
執行第一個操作兩次，p = "" 、 s = "c" 、 t = "ba"。
執行第二個操作兩次，p = "ab" 、 s = "c" 、 t = ""。
執行第一個操作一次，p = "ab" 、 s = "" 、 t = "c"。
執行第二個操作一次，p = "abc" 、 s = "" 、 t = ""。
範例 3：
輸入： s = "bdda"
輸出： "addb"
解釋： 令 p 代表著寫在紙上的字串。
一開始 p = "" 、 s = "bdda" 、 t = ""。
執行第一個操作四次，p = "" 、 s = "" 、 t = "bdda"。
執行第二個操作四次，p = "addb" 、 s = "" 、 t = ""。
解題思維：
可以看到為了讓字典序最小，第一個字元需要是 s 中字典序最小的字元（如果有多個，則取最靠左的，也就是最靠近 s 開頭）。而第二個字元則需要是 t 的尾端以及 s 中剩下字元的最小者（如果 t 的尾端與 s 中剩餘字元最小者相同，則應先取 t 的尾端）……剩下的字元基本上與第二個字元的邏輯一致。證明方式很單純，用反證法即可（為了敘述簡潔，故在此省略）。
因此我們需要可以知道在任意位置之後（含）的最小字元為何，而為了解決這個問題我們可以定義一個陣列 D，其中 D[i] 代表著 s[i] 、 s[i + 1] 、…… 之中的最小字元。則我們可以看到反著掃過 s（即由右至左）便可以求出各個 D[i] 之值，即 D[i] = min(D[i + 1], s[i])（除了 s 最後一個字元以外）。
接著我們再由左至右掃過一次 s 中所有字元，然後按照一開始提及的策略即可：而當現在有一字元 s[i]，不符合策略執行的條件時，則直接丟到 t 的尾端；如果 t 的尾端或 s[i] 符合最小之條件，則取對應字元。最後所有字元掃過、t 也被清空之後，即可得到字典序最小的字串。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
