一、题目
给你一个长度为 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 。
二、示例
2.1> 示例 1：
【输入】nums = [1,0,2]
【输出】true
【解释】有 1 个全局倒置，和 1 个局部倒置。
2.2> 示例 2：
【输入】nums = [1,2,0]
【输出】false
【解释】有 2 个全局倒置，和 1 个局部倒置。
提示：
- n == nums.length
-
1<= n <=5000 -
0<= nums[i] <n -
nums中的所有整数 互不相同 -
nums是范围[0, n - 1]内所有数字组成的一个排列
三、解题思路
3.1> 根据前缀的最大值来判断
根据题目描述，我们可以得到如下结论：
如果是局部倒置，那么一定就是全局倒置。所以，全局倒置是包含局部倒置的。
那么我们就可以将解题视角放在非局部倒置的全局倒置上。换句话说，也就是—— 非相邻数字是否满足递增。 具体操作如下图所示：
3.2> 根据偏移的差值来判断
由于题目中已经给出了如下一个关键条件：
数组
nums长度为n，并且数字是由0到n-1构成的。
所以，就可以通过nums[i]-i计算出i位置的元素与有序后的位置之间的差值：
【差值等于0】表示元素i所在的位置就是排序后的位置。
【差值等于1】表示元素1所在的位置向前1位或向后1位。
【其他情况】表示元素所在位置偏差大于1位，也就是出现了全局倒置并且非局部倒置的情况。
具体操作如下图所示：
四、代码实现
4.1> 根据前缀的最大值来判断
class Solution {
public boolean isIdealPermutation(int[] nums) {
int max = nums[0];
for (int i = 2; i < nums.length; i++) {
if (nums[i] < max) return false;
max = Math.max(max, nums[i - 1]);
}
return true;
}
}
4.2> 根据偏移的差值来判断
class Solution {
public boolean isIdealPermutation(int[] nums) {
for (int i = 0; i < nums.length; i++)
if (Math.abs(nums[i] - i) > 1) return false;
return true;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(o)/ ~ 「干货分享，每天更新」
网友评论