775.全局倒置与局部倒置.md

775.全局倒置与局部倒置

/*
 * @lc app=leetcode.cn id=775 lang=typescript
 *
 * [775] 全局倒置与局部倒置
 */

// @lc code=start
function isIdealPermutation(nums: number[]): boolean {}
// @lc code=end

解法 1: 归并排序

function isIdealPermutation(nums: number[]): boolean {
  const n = nums.length
  let res1 = 0,
    res2 = 0

  for (let i = 0; i < n - 1; i++) {
    if (nums[i] > nums[i + 1]) res2++
  }
  const c: number[] = []
  const dfs = (l: number, r: number) => {
    if (l === r) return
    const m = (l + r) >> 1
    dfs(l, m)
    dfs(m + 1, r)
    for (let i = m + 1; i <= r; i++) {
      let a = l,
        b = m
      while (a < b) {
        const m = (a + b) >> 1
        if (nums[m] < nums[i]) {
          a = m + 1
        } else {
          b = m
        }
      }
      if (nums[a] > nums[i]) res1 += m - a + 1
    }
    let i = l,
      j = m + 1,
      ss = 0
    while (i <= m && j <= r) {
      if (nums[i] > nums[j]) {
        c[ss++] = nums[j++]
      } else {
        c[ss++] = nums[i++]
      }
    }
    while (i <= m) c[ss++] = nums[i++]
    while (j <= r) c[ss++] = nums[j++]
    for (let i = 0; i < ss; i++) {
      nums[i + l] = c[i]
    }
  }
  dfs(0, n - 1)

  return res1 === res2
}

解法 2: 统计全局倒置中是否有非局部倒置

从题意可知，局部倒置一定是全局倒置，但全局倒置并不一定是局部倒置，所以要判断两者是否相等，只要看看全局倒置中是否有非局部倒置即可。

可以通过维护一个小于 i-1 前缀最大值 max，然后判断当前值是否小于 max，如果小于 max 既存在一个非局部倒置的全局倒置。

function isIdealPermutation(nums: number[]): boolean {
  let n = nums.length,
    max = -1
  for (let i = 1; i < n; i++) {
    if (nums[i] < max) return false
    max = Math.max(max, nums[i - 1])
  }
  return true
}

Case

test.each([
  { input: { nums: [1, 0, 2] }, output: true },
  { input: { nums: [1, 2, 0] }, output: false },
])('input: nums = $input.nums', ({ input: { nums }, output }) => {
  expect(isIdealPermutation(nums)).toEqual(output)
})