775. 全局倒置与局部倒置

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

暴力法

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

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;
};

LeetCode

作者：Kart Jim

链接：https://github.com/can-dy-jack/delicate/2021/07/04/leetcode/775. 全局倒置与局部倒置/

来源：Hexo

上一篇函数式编程

下一篇 547. 省份数量