【2022-11-16每日一题】775. 全局倒置与局部倒置[Medium]
2022-11-16
3分钟阅读时长
2022-11-16每日一题：775. 全局倒置与局部倒置
难度：Medium
标签：数组 、 数学
给你一个长度为 n 的整数数组 nums ，表示由范围 [0, n - 1] 内所有整数组成的一个排列。
全局倒置 的数目等于满足下述条件不同下标对 (i, j) 的数目：
0 <= i < j < nnums[i] > nums[j]
局部倒置 的数目等于满足下述条件的下标 i 的数目：
0 <= i < n - 1nums[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.length1 <= n <= 50000 <= nums[i] < nnums中的所有整数 互不相同nums是范围[0, n - 1]内所有数字组成的一个排列
方法一：维护前缀最大值
一个局部倒置一定是一个全局倒置，全局倒置的数量一定大于等于局部倒置的数量。
func isIdealPermutation(nums []int) bool {
mx := 0 // 记录nums[0,..i−2]前缀最大值
for i := 2; i < len(nums); i++ {
mx = max(mx, nums[i-2]) // 计算前缀最大值
// mx 和 nums[i] 不相邻
if mx > nums[i] {
return false
}
}
return true
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
复杂度分析
- 时间复杂度 O(n)，空间复杂度 O(1)。其中 n 为数组
nums的长度。
方法二：维护后缀最小值
func isIdealPermutation(nums []int) bool {
n := len(nums)
minSuffix := nums[n-1] // 记录后缀最小值
for i := n-3; i >= 0; i-- {
minSuffix = min(minSuffix, nums[i+2]) // 计算后缀最小值
// nums[i] 和 minSuffix 不相邻
if nums[i] > minSuffix {
return false
}
}
return true
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
复杂度分析
时间复杂度：O(n)，其中 n 是 nums 的长度。
空间复杂度：O(1)，只使用到常数个变量空间。
方法三：归纳证明
func isIdealPermutation(nums []int) bool {
for i, v := range nums {
if abs(i-v) > 1 {
return false
}
}
return true
}
func abs(x int) int {
if x > 0 {
return x
}
return -x
}
复杂度分析
时间复杂度：O(n)，其中 n 是 nums 的长度。
空间复杂度：O(1)，只使用到常数个变量空间。
方法四：树状数组
func isIdealPermutation(nums []int) bool {
n := len(nums)
tree := newBinaryIndexedTree(n)
cnt := 0
for i, v := range nums {
if i < n-1 && v > nums[i+1] {
cnt++
}
cnt -= (i - tree.query(v))
if cnt < 0 {
break
}
tree.update(v+1, 1)
}
return cnt == 0
}
type BinaryIndexedTree struct {
n int
c []int
}
func newBinaryIndexedTree(n int) BinaryIndexedTree {
c := make([]int, n+1)
return BinaryIndexedTree{n, c}
}
func (this BinaryIndexedTree) update(x, delta int) {
for x <= this.n {
this.c[x] += delta
x += x & -x
}
}
func (this BinaryIndexedTree) query(x int) int {
s := 0
for x > 0 {
s += this.c[x]
x -= x & -x
}
return s
}
复杂度分析
- 时间复杂度 O(n×logn)，空间复杂度 O(n)。其中 n 为数组 nums 的长度。