leetcode775 全局倒置与局部倒置

题目

分析

局部倒置：理解为相邻两个值，前者大于后者。
全局倒置：不一定相邻两个值，前者大于后者。
根据上述内容可以得到，全局倒置的数量 >= 局部倒置的数量。
取等号的情况，就是局部倒置的位置，例如A[3] > A[4]，那么4位置之后就再也没有比A[4]小的值了，且3位置之前也不会有比A[3]大的值，否则全局倒置的数量就会大于局部倒置的数量。所以我们如果交换所有的局部倒置的位置，那么就会形成一个单调递增序列。如果序列不是单调递增，那么说明全局倒置数量大于局部倒置数量。

代码

class Solution {
public:
    bool isIdealPermutation(vector<int>& nums) {

        int cur_max = -1;
        for (int i = 1; i < nums.size(); i++){
            if (nums[i] < nums[i - 1]){
                swap(nums[i], nums[i - 1]);
                i++;
            }
        }

        for (int i = 1; i < nums.size(); i++){
            if (nums[i] < nums[i - 1]){
                return false;
            }
        }

        return true;
    }
};