LeetCode·每日一题·775.全局倒置与局部倒置·模拟

作者：小迅
链接：https://leetcode.cn/problems/global-and-local-inversions/solutions/1973287/mo-ni-zhu-shi-chao-ji-xiang-xi-by-xun-ge-9npc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

 

示例

 

思路

一个局部倒置一定是一个全局倒置，因此要判断数组中局部倒置的数量是否与全局倒置的数量相等，只需要检查有没有非局部倒置就可以了。这里的非局部倒置指的是 nums[i] > nums[j]，其中 i < j - 1。

朴素的判断方法需要两层循环，设 n 是 nums 的长度，那么该方法的时间复杂度为 O(n^2)，无法通过。

也可以使用一次遍历进行判断

代码

 
#define MIN(a, b) ((a) < (b) ? (a) : (b))
 
bool isIdealPermutation(int* nums, int numsSize) {
    int minSuff = nums[numsSize - 1];//保存最小值
    for (int i = numsSize - 3; i >= 0; i--) {//寻找非局部
        if (nums[i] > minSuff) {
            return false;
        }
        minSuff = MIN(minSuff, nums[i + 1]);//每次保存最小值
    }
    return true;
}
 
作者：小迅
链接：https://leetcode.cn/problems/global-and-local-inversions/solutions/1973287/mo-ni-zhu-shi-chao-ji-xiang-xi-by-xun-ge-9npc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。