775. 全局倒置与局部倒置
给你一个长度为 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 。
转化
题目要求判断数组中全局倒置是否与局部倒置数量相同。由于局部倒置包含在全局倒置中。所以我们只需判断在全局倒置中是否存在非局部倒置即可。
- 即
- 0 <= i < i+1 < j < n
- nums[i] > nums[j]
class Solution {
public:
bool isIdealPermutation(vector<int>& nums) {
int maxnum=nums[0];
for(int i=2;i<nums.size();i++){
if(nums[i]<maxnum){
return false;
}
maxnum=max(maxnum,nums[i-1]);
}
return true;
}
};
标签:775,nums,局部,倒置,数目,全局
From: https://www.cnblogs.com/SkyDusty/p/16895660.html