數(shù)組 A 是 [0, 1, ..., N - 1] 的一種排列，N 是數(shù)組 A 的長度。全局倒置指的是 i,j 滿足 0 <= i < j < N 并且 A[i] > A[j] ，局部倒置指的是 i 滿足 0 <= i < N 并且 A[i] > A[i+1] 。

當數(shù)組 A 中全局倒置的數(shù)量等于局部倒置的數(shù)量時，返回 true 。

示例 :

輸入: A = [1,0,2]
輸出: true
解釋: 有 1 個全局倒置，和 1 個局部倒置。
示例 2:

輸出: false
解釋: 有 2 個全局倒置，和 1 個局部倒置。

注意:

• A 是 [0, 1, ..., A.length - 1] 的一種排列
• A 的長度在 [1, 5000]之間
  這個問題的時間限制已經減少了。

思路:

1. 局部倒置屬于全局倒置
2. 存在非局部倒置的全局倒置時返回false(即間隔一位元素大于)
3. A是從0開始不間斷序列的一種排序
4. 時間限制極短
5. 記錄一種簡潔高效的寫法,傳送門

代碼:

    public boolean isIdealPermutation(int[] A) {
        for (int i = 0; i < A.length; i++) {
            if (A[i] - i > 1 || A[i] - i < -1)
                return false;
        }
        return true;
    }

總結:

• 由于序列不間斷,當存在一個數(shù)偏離升序排序時兩單位的位置時,必然存在非局部倒置的全局倒置
• 代碼復制,小腦瓜子能看出點端倪,寫出來就難咯