LeetCode 775. Global and Local I

数组 A 是 [0, 1, ..., N - 1] 的一种排列，N 是数组 A 的长度。全局倒置指的是 i,j 满足 0 <= i < j < N 并且 A[i] > A[j] ，局部倒置指的是 i 满足 0 <= i < N 并且 A[i] > A[i+1] 。

当数组 A 中全局倒置的数量等于局部倒置的数量时，返回 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;
    }

总结:

• 由于序列不间断,当存在一个数偏离升序排序时两单位的位置时,必然存在非局部倒置的全局倒置
• 代码复制,小脑瓜子能看出点端倪,写出来就难咯