文章目录
题目
标题和出处
标题：全局倒置与局部倒置
难度
6 级
题目描述
要求
给你一个长度为 n \texttt{n} n 的整数数组 nums \texttt{nums} nums，表示在 [0, n - 1] \texttt{[0, n - 1]} [0, n - 1] 范围内的所有整数的一个排列。
全局倒置的数量是满足以下条件的不同的下标对 (i, j) \texttt{(i, j)} (i, j) 的数量：
- 0 ≤ i < j < n \texttt{0} \le \texttt{i} < \texttt{j} < \texttt{n} 0≤i<j<n
- nums[i] > nums[j] \texttt{nums[i]} > \texttt{nums[j]} nums[i]>nums[j]
局部倒置的数量是满足以下条件的不同的下标 i \texttt{i} i 的数量：
- 0 ≤ i < n - 1 \texttt{0} \le \texttt{i} < \texttt{n - 1} 0≤i<n - 1
- nums[i] > nums[i + 1] \texttt{nums[i]} > \texttt{nums[i + 1]} nums[i]>nums[i + 1]
当全局倒置的数量等于局部倒置的数量时，返回 true \texttt{true} true。
示例
示例 1：
输入：
nums
=
[1,0,2]
\texttt{nums = [1,0,2]}
nums = [1,0,2]
输出：
true
\texttt{true}
true
解释：有
1
\texttt{1}
1 个全局倒置和
1
\texttt{1}
1 个局部倒置。
示例 2：
输入：
nums
=
[1,2,0]
\texttt{nums = [1,2,0]}
nums = [1,2,0]
输出：
false
\texttt{false}
false
解释：有
2
\texttt{2}
2 个全局倒置和
1
\texttt{1}
1 个局部倒置。
数据范围
- n = nums.length \texttt{n} = \texttt{nums.length} n=nums.length
- 1 ≤ n ≤ 10 5 \texttt{1} \le \texttt{n} \le \texttt{10}^\texttt{5} 1≤n≤105
- 0 ≤ nums[i] < n \texttt{0} \le \texttt{nums[i]} < \texttt{n} 0≤nums[i]<n
- nums \texttt{nums} nums 中的所有整数都是不同的
- nums \texttt{nums} nums 是在 [0, n - 1] \texttt{[0, n - 1]} [0, n - 1] 范围内的所有整数的一个排列
解法一
思路和算法
根据全局倒置与局部倒置的定义可知，局部倒置一定是全局倒置，因此如果全局倒置的数量等于局部倒置的数量，则每个全局倒置一定是局部倒置，即对于任意 0 ≤ i < j < n 0 \le i<j< n 0≤i<j<n，当 j − i ≥ 2 j-i \ge 2 j−i≥2 时一定有 nums [ i ] < nums [ j ] \textit{nums}[i]<\textit{nums}[j] nums[i]<nums[j]。
朴素的解法是对于 [ 0 , n − 2 ) [0, n-2) [0,n−2) 区间中的每个 i i i，遍历 [ i + 2 , n ) [i+2, n) [i+2,n) 区间中的每个 j j j，如果发现 nums [ i ] > nums [ j ] \textit{nums}[i]>\textit{nums}[j] nums[i]>nums[j]，则此时的 ( i , j ) (i, j) (i,j) 是全局倒置但不是局部倒置，返回 false \text{false} false。如果遍历结束时没有发现 nums [ i ] > nums [ j ] \textit{nums}[i]>\textit{nums}[j] nums[i]>nums[j]，则返回 true \text{true} true。该解法的时间复杂度是 O ( n 2 ) O(n^2) O(n2)。
注意到对于任意 2 ≤ j < n 2 \le j<n 2≤j<n，只要存在一个 i i i 满足 0 ≤ i ≤ j − 2 0 \le i \le j-2 0≤i≤j−2 且 nums [ i ] > nums [ j ] \textit{nums}[i]>\textit{nums}[j] nums[i]>nums[j]，即存在一组 ( i , j ) (i, j) (i,j) 是全局倒置但不是局部倒置。因此，对于 0 ≤ i < n − 2 0 \le i<n-2 0≤i<n−2，令 maxValue \textit{maxValue} maxValue 表示 nums [ 0 ] \textit{nums}[0] nums[0] 到 nums [ i ] \textit{nums}[i] nums[i] 中的最大值，如果 maxValue > nums [ i + 2 ] \textit{maxValue}>\textit{nums}[i+2] maxValue>nums[i+2]，即可返回 false \text{false} false。如果遍历结束时没有发现 maxValue > nums [ i + 2 ] \textit{maxValue}>\textit{nums}[i+2] maxValue>nums[i+2] 的情况，则返回 true \text{true} true。使用该解法，可以将时间复杂度降低到 O ( n ) O(n) O(n)。
代码
class Solution {
public boolean isIdealPermutation(int[] nums) {
int n = nums.length;
int maxValue = -1;
for (int i = 0; i < n - 2; i++) {
maxValue = Math.max(maxValue, nums[i]);
if (maxValue > nums[i + 2]) {
return false;
}
}
return true;
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是数组 nums \textit{nums} nums 的长度。需要遍历数组一次。
-
空间复杂度： O ( 1 ) O(1) O(1)。
解法二
思路和算法
该解法基于一个事实：长度为 n n n 的数组 nums \textit{nums} nums 的全局倒置的数量等于局部倒置的数量，其充分必要条件是对于任意 0 ≤ i < n 0 \le i<n 0≤i<n，都有 ∣ nums [ i ] − i ∣ ≤ 1 \big|\textit{nums}[i]-i\big| \le 1 ∣∣nums[i]−i∣∣≤1。
基于上述事实，可以得到一个简单的解法：遍历数组 nums \textit{nums} nums，对于任意 0 ≤ i < n 0 \le i<n 0≤i<n，如果发现 ∣ nums [ i ] − i ∣ > 1 \big|\textit{nums}[i]-i\big|>1 ∣∣nums[i]−i∣∣>1，即返回 false \text{false} false，如果对所有的 i i i 都有 ∣ nums [ i ] − i ∣ ≤ 1 \big|\textit{nums}[i]-i\big| \le 1 ∣∣nums[i]−i∣∣≤1，则返回 true \text{true} true。
证明
对于上述命题，需要从必要性和充分性两个方面证明。
- 必要性
已知长度为 n n n 的数组 nums \textit{nums} nums 的全局倒置的数量等于局部倒置的数量。假设存在 0 ≤ i < n 0 \le i<n 0≤i<n，使得 ∣ nums [ i ] − i ∣ > 1 \big|\textit{nums}[i]-i\big|>1 ∣∣nums[i]−i∣∣>1。
如果 nums [ i ] − i > 1 \textit{nums}[i]-i>1 nums[i]−i>1，等价于 nums [ i ] − i ≥ 2 \textit{nums}[i]-i \ge 2 nums[i]−i≥2，在下标 i i i 的右侧共有 n − i − 1 n-i-1 n−i−1 个元素，但是比 nums [ i ] \textit{nums}[i] nums[i] 大的元素不会超过 n − i − 3 n-i-3 n−i−3 个，因此至少有 2 2 2 个大于 nums [ i ] \textit{nums}[i] nums[i] 的元素在下标 i i i 的左侧，其中至少有 1 1 1 个元素和 nums [ i ] \textit{nums}[i] nums[i] 不相邻，该元素和 nums [ i ] \textit{nums}[i] nums[i] 即为一组全局倒置但不是局部倒置，因此全局倒置的数量大于局部倒置的数量，与已知条件矛盾。
如果 i − nums [ i ] > 1 i-\textit{nums}[i]>1 i−nums[i]>1，等价于 i − nums [ i ] ≥ 2 i-\textit{nums}[i] \ge 2 i−nums[i]≥2，在下标 i i i 的左侧共有 i i i 个元素，但是比 nums [ i ] \textit{nums}[i] nums[i] 小的元素不会超过 i − 2 i-2 i−2 个，因此至少有 2 2 2 个小于 nums [ i ] \textit{nums}[i] nums[i] 的元素在下标 i i i 的右侧，其中至少有 1 1 1 个元素和 nums [ i ] \textit{nums}[i] nums[i] 不相邻，该元素和 nums [ i ] \textit{nums}[i] nums[i] 即为一组全局倒置但不是局部倒置，因此全局倒置的数量大于局部倒置的数量，与已知条件矛盾。
综上所述，如果存在 0 ≤ i < n 0 \le i<n 0≤i<n，使得 ∣ nums [ i ] − i ∣ > 1 \big|\textit{nums}[i]-i\big|>1 ∣∣nums[i]−i∣∣>1，则一定会存在一组全局倒置不是局部倒置，与已知条件矛盾。因此如果长度为 n n n 的数组 nums \textit{nums} nums 的全局倒置的数量等于局部倒置的数量，则对于任意 0 ≤ i < n 0 \le i<n 0≤i<n，都有 ∣ nums [ i ] − i ∣ ≤ 1 \big|\textit{nums}[i]-i\big| \le 1 ∣∣nums[i]−i∣∣≤1。
- 充分性
对于任意 0 ≤ i < n 0 \le i<n 0≤i<n，都有 ∣ nums [ i ] − i ∣ ≤ 1 \big|\textit{nums}[i]-i\big| \le 1 ∣∣nums[i]−i∣∣≤1。
如果存在 0 ≤ i < n − 1 0 \le i<n-1 0≤i<n−1 满足 nums [ i ] = i + 1 \textit{nums}[i]=i+1 nums[i]=i+1，则必有 nums [ i + 1 ] = i \textit{nums}[i+1]=i nums[i+1]=i，否则一定会出现 ∣ nums [ n − 1 ] − ( n − 1 ) ∣ > 1 \big|\textit{nums}[n-1]-(n-1)\big| > 1 ∣∣nums[n−1]−(n−1)∣∣>1。
如果存在 0 ≤ i < n − 1 0 \le i<n-1 0≤i<n−1 满足 nums [ i ] = i + 1 \textit{nums}[i]=i+1 nums[i]=i+1 且 nums [ i + 1 ] ≠ i \textit{nums}[i+1] \ne i nums[i+1]=i，则必有 nums [ i + 1 ] = i + 2 \textit{nums}[i+1]=i+2 nums[i+1]=i+2，根据数学归纳法可知，对任意 i ≤ j < n − 1 i \le j<n-1 i≤j<n−1 都有 nums [ j ] = j + 1 \textit{nums}[j]=j+1 nums[j]=j+1，此时 nums [ n − 1 ] < n − 2 \textit{nums}[n-1]<n-2 nums[n−1]<n−2，因此 ∣ nums [ n − 1 ] − ( n − 1 ) ∣ > 1 \big|\textit{nums}[n-1]-(n-1)\big| > 1 ∣∣nums[n−1]−(n−1)∣∣>1，与已知条件矛盾。因此如果 nums [ i ] = i + 1 \textit{nums}[i]=i+1 nums[i]=i+1，则必有 nums [ i + 1 ] = i \textit{nums}[i+1]=i nums[i+1]=i。
同理可得，如果存在 0 < i ≤ n − 1 0<i \le n-1 0<i≤n−1 满足 nums [ i ] = i − 1 \textit{nums}[i]=i-1 nums[i]=i−1，则必有 nums [ i − 1 ] = i \textit{nums}[i-1]=i nums[i−1]=i，否则一定会出现 ∣ nums [ 0 ] − 0 ∣ > 1 \big|\textit{nums}[0]-0\big| > 1 ∣∣nums[0]−0∣∣>1。
由于对任意 0 ≤ i < n 0 \le i<n 0≤i<n 都有 ∣ nums [ i ] − i ∣ ≤ 1 \big|\textit{nums}[i]-i\big| \le 1 ∣∣nums[i]−i∣∣≤1，因此全局倒置的数量等于局部倒置的数量。
代码
class Solution {
public boolean isIdealPermutation(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; i++) {
if (Math.abs(nums[i] - i) > 1) {
return false;
}
}
return true;
}
}
复杂度分析
-
时间复杂度： O ( n ) O(n) O(n)，其中 n n n 是数组 nums \textit{nums} nums 的长度。需要遍历数组一次。
-
空间复杂度： O ( 1 ) O(1) O(1)。