难度: Medium
给你一个长度为 n 的整数数组 nums ，表示由范围 [0, n - 1] 内所有整数组成的一个排列。
全局倒置 的数目等于满足下述条件不同下标对 (i, j) 的数目：
0 <= i < j < nnums[i] > nums[j]局部倒置 的数目等于满足下述条件的下标 i 的数目：
0 <= i < n - 1nums[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.length1 <= n <= 1050 <= nums[i] < nnums 中的所有整数 互不相同nums 是范围 [0, n - 1] 内所有数字组成的一个排列运行时间: 42 ms
内存: 26.0 MB
class Solution:
def isIdealPermutation(self, nums: List[int]) -> bool:
prev_max = nums[0] # j
for i in range(1, len(nums)-1):
if prev_max > nums[i+1]:
return False
prev_max = max(prev_max, nums[i])
return True
# 首先当j = i + 1时，可以看出，一个局部翻转就是一个全局翻转。那么如果要使得局部翻转
# 和全局翻转的个数相等，那么必须要求全局翻转也是一个局部翻转。所以，对于任意的j > i + 1，
# 不能存在A[i] > A[j]，即需要满足A[i] <= A[j].
# 从上面的关系可以看出，我们必须使max(A[:i]) <= A[i + 2]。
class Solution:
def isIdealPermutation(self, nums: List[int]) -> bool:
for i, num in enumerate(nums):
# 检查数组中是否存在任何非局部的全局倒置, not
if abs(num - i) > 1:
return False
return True
# 上面的想法并没有好好的利用题目给出的数字是0-N-1这个条件。所以我们继续思考，
# 如果原来的顺序是0-N-1，那么如何交换两个数字才能满足局部翻转的个数等于全局翻转呢？
# 答案当然是只翻转相邻的两个元素。
# 否则会构造出来一个不是局部翻转的全剧翻转。所以i的位置上只能放A[i-1],A[i],A[i+1]。
# 考虑一个简单的例子，数组 nums = [1, 0, 2]。
# 根据 abs(num - i) != 0 这个条件，我们来检查每个元素：
# 对于 i = 0，num = 1，abs(1 - 0) = 1 != 0，条件不满足，应该返回 False。
# 对于 i = 1，num = 0，abs(0 - 1) = 1 != 0，同样，条件不满足。
# 然而，这个数组 [1, 0, 2] 实际上是一个理想的排列，因为它的全局倒置数量（1对）
# 和局部倒置数量（1对）是相等的。全局倒置是 (1, 0)，局部倒置也是 (1, 0)。
这个题解的核心思路基于局部倒置一定是全局倒置的特性。如果要使全局倒置的数量等于局部倒置的数量，那么不能存在非局部的全局倒置（即跨越超过一个元素的倒置）。此题解通过检查每个元素的索引和值之间的差的绝对值是否大于1来判断是否存在非局部的全局倒置。如果所有元素的值与其索引位置差的绝对值都不大于1，则表明所有的全局倒置都是局部倒置，返回True；否则，存在非局部的全局倒置，返回False。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def isIdealPermutation(self, nums: List[int]) -> bool:
for i, num in enumerate(nums):
# 检查数组中是否存在任何非局部的全局倒置
if abs(num - i) > 1:
return False
return True # 如果没有发现非局部全局倒置，则返回True
局部倒置指的是在数组中相邻的两个元素满足倒置条件，即在数组的连续位置i和i+1，满足nums[i] > nums[i + 1]。由于局部倒置的两个元素位置相邻，自然满足全局倒置的条件，即存在一对下标i和j（这里j=i+1），使得nums[i] > nums[j]。因此，所有的局部倒置都是全局倒置的特殊情况，即局部倒置是全局倒置的一个子集。
在数组nums中，如果一个元素的值与它的索引位置的差的绝对值大于1，这意味着该元素在数组中的实际位置与它应该在的位置相差超过一个位置。这种情况下，它很可能与不相邻的其他元素构成倒置，因此可能存在非局部的全局倒置。而如果每个元素的值与其索引位置的差的绝对值都不大于1，说明每个元素都不会跨越超过一个位置，仅可能与其相邻的元素构成倒置，即所有全局倒置都是局部倒置。因此，此检查足以判断是否存在非局部倒置。
这种方法实际上只针对是否存在非局部的全局倒置进行了检测。它基于的思想是如果一个元素与其索引的差的绝对值不超过1，那么它只可能与紧邻的一个元素构成倒置（局部倒置），而不会与更远的元素构成倒置。因此，这种检测主要是为了确认所有的全局倒置是否都是局部倒置。如果满足这一条件，则全局倒置数量等于局部倒置数量，否则，全局倒置数量大于局部倒置数量。这种方法没有直接计算每一种可能的全局倒置，而是通过排除存在非局部倒置的可能性来间接达到目的。