Max Distance

题目描述

Given an array A of integers, find the maximum of j - i subjected to the constraint of A[i] <= A[j].

If there is no solution possible, return -1.

解题方法

brute force

O(n^2)的做法很容易想到

不行就sort大法

O(nlogn)

sort, 而且sort的时候我们还有保存原有的元素的index

Solution

class Solution:
    # @param A : tuple of integers
    # @return an integer
    def maximumGap(self, A):
        length = len(A)
        max_gap = 0

        index_map = {}
        for idx, num in enumerate(A):
            if num in index_map:
                index_map[num].append(idx)
            else:
                index_map[num] = [idx]
        A = sorted(A)

        min_left = []
        max_right = []

        for num in A:
            if not min_left:
                min_left.append(index_map[num][0])
            else:
                new_min = min(index_map[num][0],min_left[-1])
                min_left.append(new_min)

        for i in range(len(A)-1, -1, -1):
            if not max_right:
                max_right.append(index_map[A[i]][-1])
            else:
                new_max = max(index_map[A[i]][-1],max_right[-1])
                max_right.append(new_max)
        max_right.reverse()

        for i in range(len(A)):
            max_gap = max(max_gap, max_right[i] - min_left[i])

        return max_gap

Reference