Make array Non-Decreasing in At

这题是一道新题对我来说， 我一开始的想法是用Bubble sort来做，【其实没什么头绪，只是想到Bubble sort的一个经典套路就是设置一个boolean来判断是不是already sorted 的array， 然后sort。 我想如果swap的iteration超过1次就return false。 】但是好像是不对的

我后来换了一个方法，就是先判断array是不是已经sorted了。如果已经sorted，return true。

否则的话，找到第一个decreasing element. 然后跳出循环。

比如 1,2,3,6,5,8 会在5跳出循环。

然后从array的后面往前走，找到最小的element that's bigger than first decreasing element

就是6

然后与first decreasing element swap.

之后再check一下array是不是sorted。

唉。。。

onsite完LiveAction发现我这道题的答案写错了。。

现场重新做了一遍 O(NlogN)办法是直接sort 然后和原数组比所有对应位置的element

O(n)方法是双指针，一个从前走一个后往前走。当碰到wrong order时候两个swap一下。

然后再traverse一遍array看看是不是sorted.