【leetcode】Global and Local Inversions

题目如下：

We have some permutation A of [0, 1, ..., N - 1], where N is the length of A.

The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].

The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].

Return true if and only if the number of global inversions is equal to the number of local inversions.

Example 1:

Input: A = [1,0,2]

Output: true

Explanation: There is 1 global inversion, and 1 local inversion.

Example 2:

Input: A = [1,2,0]

Output: false

Explanation: There are 2 global inversions, and 1 local inversion.

Note:

A will be a permutation of [0, 1, ..., A.length - 1].

A will have length in range [1, 5000].

The time limit for this problem has been reduced.

解题思路：这是一个非常有趣的题目。我最初的想法是用一个二层的循环计算出Global的值，然后好Local比较，但是O(n^2)的复杂度显然是不行的，然后我各种优化但是得到的依旧是冷冰冰的Time Exceed Limit.考虑到题目只是要求判断Global是否会等于Local，机智的我果断放弃了计算出Global的值的尝试，开始寻找更巧妙的解法。皇天不负有心人，果然被我找到了。对应任意一个数字A[i]来说，它的Global一定是大于或者等于Local的，也就是说，在整个A中，只要找到任意一个A[i]满足在A[i+2]~A[N-1]里面有一个小于A[i]的数，最终整个数组的Global就一定会大于Local了。为什么不用考虑A[i+1]？无论A[i]和A[i+1]的大小关系如何，Global和Local的值要不分别加1，要么不变，所以不管。那么问题来了，怎么找到任意一个A[i]满足在A[i+2]~A[N-1]里面有一个小于A[i]的数呢？只需要依次遍历数组，找出以遍历元素中的最大值（记为max）和当前遍历到的元素的后面第二个元素(记为A[i+2])比较就行了，如果max > A[i+2] ，那么Global就一定会大于Local了。

代码如下：

class Solution(object):

    def isIdealPermutation(self, A):

        """

        :type A: List[int]

        :rtype: bool

        """

        maxV = -1

        for i in range(len(A)-2):

            if maxV == -1 or maxV < A[i]:

                maxV = A[i]

            if maxV > A[i+2]:

                return False

        return True

巴特西

【leetcode】Global and Local Inversions

最新文章

热门文章