775. 全局倒置与局部倒置

暴力法+维护最小值+数学法=循序渐进

暴力法

看到题目，没有任何技巧，直接暴力！🐶 🐶

var isIdealPermutation = function(nums) {
    for(let i = 0;i<nums.length-2;i++) {
        for(let j = i+2;j<nums.length;j++) {
            if(nums[i] > nums[j]) return false;
        }
    }
    return true;
};

维护最小值法

稍微分析一下，我们在 i 位置上，只要找到从 i+2 往后的值中有小于 i 位上的值即可；那么只需要从 i+2 往后的值中最小的值与 nums[i] 比较即可！

可以从后往前遍历，有利于保存后缀最小值。

var isIdealPermutation = function(nums) {
    let min = nums[nums.length-1];
    for(let i = nums.length-3;i>=0;i--) {
        if(nums[i] > min) return false;
        min = Math.min(min, nums[i+1]);
    }
    return true;
};

数学证明

接着分析：

• 在 i=0 的位置上，只要其大于等于 2，那就一定能在 i=2 及往后的位置中找到小于 i 的值。
• 在 i=1 的位置上，只要其大于等于 3，那就一定能在 i=3 及往后的位置中找到小于 i 的值。
• 以此类推，可以看到，只要保证 nums[i] <= i+2 即可！

/**
 * @param {number[]} nums
 * @return {boolean}
 */
var isIdealPermutation = function(nums) {
    for(let i = 0;i<nums.length;i++) {
        if(Math.abs(nums[i] - i) >= 2) return false;
    }
    return true;
};