給你一個整數(shù)?n?，按字典序返回范圍?[1, n]?內(nèi)所有整數(shù)。

你必須設(shè)計一個時間復(fù)雜度為?O(n)?且使用?O(1)?額外空間的算法。

開始被后面那句話唬住了愣是想不出來，但是冷靜下來以后，改變了思考方式：

結(jié)果是按照字典序來排列，那我按照字典序的規(guī)則每次讓前一個數(shù)加1不就行了嗎。

現(xiàn)在看是理所當(dāng)然的答案，但是開始的時候并沒有往這個方向想。能找到答案是因為我改變了思考方式，我想的不再是怎么得到整體的答案，即按照字典序排列的那一堆整數(shù)；而是得出那個整體的其中一個答案的邏輯，再把這個邏輯應(yīng)用于每一個單獨的答案。

對于這道題而言，就是怎么根據(jù)前一個數(shù)得到當(dāng)前位置的數(shù)。

通過觀察示例發(fā)現(xiàn)，字典序的+1無非兩種情況：

1. 末尾添0.

2. 正常+1.

正常+1和一個int型一樣，唯一的區(qū)別是進位的時候需要去掉后一位的0。然后進位還要分兩種情況，一種是數(shù)字加到比n大了，一種是低位等于9了。

于是就有了這個代碼：

結(jié)果9ms，算是慢的了但是沒什么優(yōu)化空間。然后就直接去看了官方的題解，發(fā)現(xiàn)......

官方題解的想法和我的想法是一致的，只是有一點有疑問：

number*10<=n真的可以認為number*10就是下一個字典序整數(shù)嗎？

我想找?guī)讉€反例，但是顯然是沒有的......那么反過來思考吧，末尾添0總共有幾種情況：

1. 進位以后。第n位等于9以后，下一個數(shù)沒有第n位，下下個數(shù)的第n位一定是0。比如1239的下一個數(shù)是124，再下一個是1240，這是字典序的規(guī)則決定的。

2. 初始值1。

第一種情況，1239既然存在就是確定小于等于n的，如果1239等于n，那么循環(huán)會直接結(jié)束，因此n一定>=1240。也就是說，num x 10絕對不會比n大。

說人話就是末尾添0還比n小的情況，只有進位以后。而字典序的規(guī)則決定了進位以后的下一個數(shù)，一定是number*10。

以上。