主題
題目連結(jié)：
題目意譯：
你被給定一個很大的整數(shù) n ，以一個字串表示，以及一個整數(shù)數(shù)字 x 。 n 每位數(shù)以及數(shù)字 x 皆在範圍 [1, 9] 之間（含左右端點），且 n 可能代表著一個負數(shù)。
你想要最大化 n 的數(shù)值，藉由將 x 插入進 n 的十進位表示法中的某個位置。你不能將 x 插入到負號的左側(cè)。
例如，如果 n = 73 且 x = 6 ，其最佳應插入於 7 和 3 中間，得到 n = 763 。
如果 n = -55 且 x = 2 ，其最佳應插入到第一個 5 的前面，得到 n = -255 。
回傳插入後所能得到的最大 n 值之字串表示法。
限制：
1 ≦ n.length ≦ 10 ^ 5
1 ≦ x ≦ 9
n 的每個位數(shù)位於範圍 [1, 9] 中。
n 是一個整數(shù)的合法表示法。
當 n 為負時，其以 '-' 作為開頭。
範例測資：
範例 1：
輸入： n = "99", x = 9
輸出： "999"
解釋： 不論你何處插入 9 結(jié)果都會一樣。
範例 2：
輸入： n = "-13", x = 2
輸出： "-123"
解釋： 你可以得到 n 為 {-213, -123, -132} 其中一者，而這三個中最大的為 -123 。
解題思維：
先討論 n 為正的情況：
可以看到 x 於 n 之中會有 n.length + 1 種插入的方式。例如 n = "88" 、 x = 9，我們會有 "988" 、 "898" 、 "889" 這三種。
而在這 n.length + 1 個可能的值中最大的，同時也是字典序最大的。
假設有兩個值 d1 、 d2，一個插入位置為 i ，另一個則為 j （i < j）。則我們可以看到當 d1[i] = x > d2[i]（k = 0 ～ i - 1，d1[k] = d2[k]）時，代表 d1 的字典序比 d2 大。而且此時也代表著只要 i < j ，所有插入位置為 j 的值之字典序皆小於 d1 。
因此，我們掃過 n 的每位數(shù) n[i]。當 n[i] < x 時，代表著我們應在此插入 x （意即把 x 放在 n[i] 前面），才可以使得字典序最大也因此所得之值最大。如果掃完所有 n[i] 之後（這樣只把 n.length 個可能看完而已），還沒有將 x 插入到 n 裡，表示我們應插入到 n 的最後面。
至於 n 為負的情況，則類似上面的論述，但是現(xiàn)在是字典序越小，值越大（因為負的程度比較小）。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
