775. 全局倒置与局部倒置

难度中等119

给你一个长度为 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 <= 5000
• 0 <= nums[i] < n
• nums 中的所有整数 互不相同
• nums 是范围 [0, n - 1] 内所有数字组成的一个排列

分析：最直观的想法就是我们分别统计全局倒置与局部倒置的数量，然后进行比对。很显然，本题中所说的全局导致其实就是逆序对，而局部倒置就是索引相隔1位的逆序对。

1.树状数组统计逆序对个数

注：在使用树状数组统计逆序对个数的时候，对于nums[i]，其实我们想要知道的是在[0,i-1]区间上有多少nums[j]>nums[i]，而树状数组适合用来统计<=nums[i]的数有多少，因此我们可以做如下处理，假设当前索引位置在idx：

        1）idx + 1 - get_sum(nums[idx])

        2）树状数组的值维护使用100000-nums[idx]，例如，nums[i]=100，那么对应维护的是100000-100=99900，nums[i+1]=50，那么对应维护的是100000-59=99950，那么我们想查找在[0,i-1]上小于nums[i]的数的个数即逆序对的个数时，我们只需要get_sum(100000-nums[i]-1)，在上述例子中为get_sum(99949)。

class Solution {
public:int tree[100005];int lowbit(int i){return i &(-i);}int get_sum(int tree[], int n, int v){int sum = 0;while(v){sum += tree[v];v -= lowbit(v);}return sum;}void update(int tree[], int v){while(v < 100005){++ tree[v];v += lowbit(v);}}bool isIdealPermutation(vector& nums) {int n = nums.size(), global_reverse_num = 0;memset(tree, 0, sizeof(tree));for(int idx = 0; idx < n; ++ idx){update(tree, nums[idx] + 1);global_reverse_num += idx + 1 - get_sum(tree, n, nums[idx] + 1) - (idx < n - 1 && nums[idx] > nums[idx + 1] ? 1 : 0);}return global_reverse_num == 0;}
};

2.归并排序统计逆序对个数

class Solution {
public:int global_reverse_num = 0;void MergeSort(vector& nums, int L, int R){if(L >= R) return;int M = (L + R) >> 1;MergeSort(nums, L, M);MergeSort(nums, M + 1, R);Merge(nums, L, M, R);}void Merge(vector& nums, int L, int M, int R){vector temp = vector(nums.size(), 0);int l = L, r = M + 1, idx = L;while(l <= M && r <= R){if(nums[l] <= nums[r]){temp[idx++] = nums[l++];}else{global_reverse_num += (M + 1 - l);temp[idx++] = nums[r++];}}while(l <= M){temp[idx++] = nums[l++];}while(r <= R){temp[idx++] = nums[r++];}for(idx = L; idx <= R; ++ idx){nums[idx] = temp[idx];}}bool isIdealPermutation(vector& nums) {int idx, n = nums.size();for(idx = 0; idx < n - 1; ++ idx){if(nums[idx] > nums[idx + 1]){-- global_reverse_num;}}MergeSort(nums, 0, n - 1);return global_reverse_num == 0;}
};

3.维护最小后缀值

        其实我们会发现，我们只需要找到一个逆序对符合索引位置相隔大于1就可以表明全局倒置个数一定大于局部倒置个数。

        因此一种更好的优化思路是，当我们在考虑nums[i]的时候，只需要在nums数组的[i+2,n-1]区间上存在j使得nums[i] > nums[j]，就可以得到答案false。那么实际上我们只需要知道nums数组的[i+2,n-1]区间上的最小值suffix_min[i+2]，只要nums[i] > suffix_min[i+2]就得到答案false。

class Solution {
public:bool isIdealPermutation(vector& nums) {int idx, n = nums.size(), local_reverse_num;int suffix_min[n + 5];suffix_min[n - 1] = nums[n - 1];for(idx = n - 2; idx >= 0; -- idx){suffix_min[idx] = min(suffix_min[idx + 1], nums[idx]);if(idx <= n - 3 && nums[idx] > suffix_min[idx + 2]){return false;}}return true;}
};