leetcode
leetcode 651 ~ 700
全局倒置与局部倒置

全局倒置与局部倒置

难度:

标签:

题目描述

代码结果

运行时间: 42 ms, 内存: 26.0 MB

/*
 * 使用 Java Stream 进行实现。
 * 思路：
 * 我们需要检查是否存在 nums[i] > nums[j] 且 j > i + 1 的情况。
 * 如果存在则返回 false，否则返回 true。
 */
import java.util.stream.IntStream;
public boolean isIdealPermutation(int[] nums) {
    return IntStream.range(0, nums.length - 2)
            .allMatch(i -> nums[i] <= nums[i + 2]);
}

解释

方法:

这个题解的核心思路基于局部倒置一定是全局倒置的特性。如果要使全局倒置的数量等于局部倒置的数量，那么不能存在非局部的全局倒置（即跨越超过一个元素的倒置）。此题解通过检查每个元素的索引和值之间的差的绝对值是否大于1来判断是否存在非局部的全局倒置。如果所有元素的值与其索引位置差的绝对值都不大于1，则表明所有的全局倒置都是局部倒置，返回True；否则，存在非局部的全局倒置，返回False。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
请解释为什么局部倒置一定是全局倒置的特例？
▷
局部倒置指的是在数组中相邻的两个元素满足倒置条件，即在数组的连续位置i和i+1，满足nums[i] > nums[i + 1]。由于局部倒置的两个元素位置相邻，自然满足全局倒置的条件，即存在一对下标i和j（这里j=i+1），使得nums[i] > nums[j]。因此，所有的局部倒置都是全局倒置的特殊情况，即局部倒置是全局倒置的一个子集。
🦆
在给定的算法中，为什么只需要检查每个元素的索引和值之间差的绝对值是否大于1就足以判断是否有非局部倒置？
▷
在数组nums中，如果一个元素的值与它的索引位置的差的绝对值大于1，这意味着该元素在数组中的实际位置与它应该在的位置相差超过一个位置。这种情况下，它很可能与不相邻的其他元素构成倒置，因此可能存在非局部的全局倒置。而如果每个元素的值与其索引位置的差的绝对值都不大于1，说明每个元素都不会跨越超过一个位置，仅可能与其相邻的元素构成倒置，即所有全局倒置都是局部倒置。因此，此检查足以判断是否存在非局部倒置。
🦆
这种方法是否考虑了所有可能的全局倒置情况，还是仅仅针对特定类型的全局倒置进行检测？
▷
这种方法实际上只针对是否存在非局部的全局倒置进行了检测。它基于的思想是如果一个元素与其索引的差的绝对值不超过1，那么它只可能与紧邻的一个元素构成倒置（局部倒置），而不会与更远的元素构成倒置。因此，这种检测主要是为了确认所有的全局倒置是否都是局部倒置。如果满足这一条件，则全局倒置数量等于局部倒置数量，否则，全局倒置数量大于局部倒置数量。这种方法没有直接计算每一种可能的全局倒置，而是通过排除存在非局部倒置的可能性来间接达到目的。

相关问题

数据流中的第 K 大元素二分查找