题目：

给你一个长度为 n 的整数数组 nums ，表示由范围 [0, n - 1] 内所有整数组成的一个排列。

全局倒置 的数目等于满足下述条件不同下标对 (i, j) 的数目：

0 <= i < j < n
nums[i] > nums[j]

局部倒置 的数目等于满足下述条件的下标 i 的数目：

0 <= i < n - 1
nums[i] > nums[i + 1]

当数组 nums 中 全局倒置 的数量等于 局部倒置 的数量时，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,0,2]
输出：true
解释：有 1 个全局倒置，和 1 个局部倒置。

示例 2：

输入：nums = [1,2,0]
输出：false
解释：有 2 个全局倒置，和 1 个局部倒置。

提示：

n == nums.length
1 <= n <= 105
0 <= nums[i] < n
nums 中的所有整数 互不相同
nums 是范围 [0, n - 1] 内所有数字组成的一个排列

解题思路：

模拟（暴力）

根据题意，遍历 nums ，定义：第一层循环下标为 i ，第二层循环下标为 j 。

只要 nums[i] > nums[j] 那么全局 g 就+1，若 j = i + 1 则 l + 1

维护最小值

其实我们可以将这题的思路转换一下，一个局部倒置必定是一个全局倒置，那么想要两个相等就必须全局倒置后面没有比他小的数，也就是 nums[i] > nums[i + 1] and nums[i] < nums[i+1:] 明白这个就能写出代码了。

我们逆序遍历，遍历的每个数是不是只有一个全局倒置，若有多个则直接返回 False

代码：

Python

模拟

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def isIdealPermutation(self, nums: List[int]) -> bool:
        g, l = 0, 0
        n = len(nums)
        for i in range(0, n - 1):
            for j in range(i + 1, n):
                x1, x2 = nums[i], nums[j]
                if i + 1 == j and x1 > x2:
                    l += 1
                    flag = True
                g += 1 if x1 > x2 else 0
        return g == l

维护最小后缀

1
2
3
4
5
6
7
8
9
10
class Solution:
    def isIdealPermutation(self, nums: List[int]) -> bool:
        min_suf = nums[-1]
        for i in range(len(nums) - 2, 0, -1):
            if nums[i - 1] > min_suf:
                return False
            min_suf = nums[i] if nums[i] < min_suf else min_suf
            # for loop 中调用function开销很大
            # min_suf = min(min_suf, nums[i])
        return True

C++

模拟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isIdealPermutation(vector<int>& nums) {
        int g = 0, l = 0;
        int n = nums.size();
        for (int i = 0; i < n - 1; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int x1 = nums[i], x2 = nums[j];
                if (i + 1 == j && x1 > x2) ++l;
                if (x1 > x2) ++g;
            }
        }
        return g == l;
    }
};

维护最小后缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isIdealPermutation(vector<int>& nums) {
        int n = nums.size();
        int suf_min = nums[n - 1];
        for (int i = n - 2; i > 0; --i) {
            if (suf_min < nums[i - 1]) return false;
            
            // if (nums[i] < suf_min) suf_min = nums[i];
            suf_min = min(nums[i], suf_min);
        }
        return true;
    }
};

注意：

无论哪个语言，在for loop(循环)中调用函数开销都是很大的，我们应该避免在 for loop 中调用函数