LeetCode-775-全局倒置与局部倒置

1、数学方法

根据题意，显然全局倒置的值大于等于局部倒置的值。因此我们不必求出具体的全局倒置的值和局部倒置的值，我们只需要证明全局倒置的值大于局部倒置的值即可。

因此我们可以从后往前进行查询，只要我们能够证明区间$[i+1,n-1]$中的最小值不仅小于$nums[i]$，而且还小于$nums[i-1]$即可说明当前的全局倒置的值一定大于局部倒置的值。

class Solution {
public:
    bool isIdealPermutation(vector<int>& nums) {
        int n = nums.size(), temp_min = nums[n - 1];
        for (int i = n - 3; i >= 0; i--) {
            if (nums[i] > temp_min) {
                return false;
            }
            temp_min = min(temp_min, nums[i + 1]);
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

2、数学归纳$$

若全局倒置大于局部倒置说明存在一个$j>i+1$令$nums[i]>nums[j]$，因此我们可以开始进行归纳：对于0而言，若全局倒置等于局部倒置则说明0前面最多不超过一个数字。1、若$nums[0]=0$，则我们需要进一步比较区间$[1,n]$是否满足条件；2、若$nums[1]=0$，则我们需要进一步比较区间$[2,n]$是否满足条件。以此类推，我们可以最终得到每个元素$nums[i]$都应满足$\left|nums[0]-0\right|\le 1$。

class Solution {
public:
    bool isIdealPermutation(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            if (abs(nums[i] - i) > 1) {
                return false;
            }
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11