嗯......沒想到還真給做出來了。

雖然最后速度還是很慢，但好在使用的額外內(nèi)存就只有一個int數(shù)組，所以空間復(fù)雜度還說得過去......但是leetcode的機器真的有點迷，本來我一堆額外的靜態(tài)方法和變量，結(jié)果提交上去只用了35M，把所有靜態(tài)方法和額外的代碼刪掉以后再提交，反而多了0.2M，執(zhí)行時間也在80到120之間反復(fù)橫跳。

結(jié)果已經(jīng)遠超預(yù)期了，本來覺得不看題解根本做不了，然后用字典序做了出來。字典序超時以后想盡各種辦法優(yōu)化，最后終于勉強進了200ms以內(nèi)，通過了。

優(yōu)化的過程中突然發(fā)現(xiàn)，所有可行的排列連在一起也是滿足字典序中的“相鄰”的。于是想到，沒必要拘泥于字典序的規(guī)則，完全可以自己定義一個規(guī)則然后只枚舉滿足條件的排列。

最后還是沒找到可以只枚舉滿足條件的排列的方法，但比起基于字典序的優(yōu)化，已經(jīng)好很多了。這是字典序優(yōu)化后的代碼，在我的機器上要用200ms左右:

然后這是新的代碼，自己的機器上是100ms左右：

所以說那些長的要死還各種if嵌套的代碼是不可取的，if多只能說明思路上就是錯的，才要考慮更多例外的情況......

都說不要死磕一道題，但有的時候我在想，如果看到某道題腦海里就有了答案，那去做這道題還有什么意義可言嗎......感覺那樣就不是學(xué)習(xí)而是記憶了。記住某道題，或者某類題的答案，下次出現(xiàn)同類就可以輕松應(yīng)對......目的是面試的話可以，但對自身思考問題的能力真的有提升嗎。

這次的收獲還是挺多的，比如學(xué)會了字典序，還有在思考不出結(jié)果時的正確做法。

簡而言之，想不出辦法不意味著智商低，知識量不夠，僅僅只是理解不夠深刻。字典序算法到底是怎么回事，我到現(xiàn)在還是沒完全理解，但我依舊在理解字典序的過程中獲得了靈感。

一開始想不通為什么后面要reverse一下，想不通為什么reverse可以代替排序......過了很久才明白，reverse對于這一次的調(diào)用確實沒有任何意義，它是在為下一次調(diào)用做準(zhǔn)備。

于是我明白了，要從更加宏觀的角度去思考，單獨去看某一行代碼起到了什么作用，很多時候是看不出來的，減去這一行，看看最終的結(jié)果有什么變化，就可以知道它的真正作用了。

排序的方法暫時可以放一下了，還得用回溯接著磕這道題。