原题链接:
https://leetcode.cn/problems/global-and-local-inversions/
本质是一个判断逆序对的问题

法1 推理

全局倒置 全局内 逆序的数对
局部倒置 相邻的逆序对
因此局部倒置 一定是 全局倒置
即 全局倒置 >= 局部倒置
因此全局逆序对的产生方式 必须与局部逆序对相同
即 存在所有逆序对必须都是相邻逆序 如果不是相邻逆序 则为false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
package main

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func isIdealPermutation(nums []int) bool {
	mx := nums[0]
    n := len(nums)
	for i:=2 ; i < n ; i++{
        mx = max(mx,nums[i-2])
        if mx > nums[i]{
            return false
        }
    } 

	return true
}

法2 树状数组