975. Odd Even Jump - notruilin/LeetCode GitHub Wiki

在一个序列A上jump（jump标号从第1次开始），在奇数次jump时是从i跳到j满足i < j && A[i] <= A[j] && A[j]最小，即A[i]之后比它大的最小的数；在偶数次jump时从i跳到比它小的最大的数。问有多少index可以跳到A的最后一位（1 <= A.length <= 20000） 如果对于每一个i，我们都知道odd[i]和even[i]，即在奇数次和偶数次时从i分别会跳到哪里，就可以做一个O(n)的递推 goodForOdd[i] == True表示从i进行第奇数次跳跃可以到达最后一位，初始化最后一位的goodForOdd和goodForEven为True，从后向前倒退 注意只有goodForOdd[i] == True时ans + 1，因为只能从奇数次开始

    goodForOdd = [False] * len(A)
    goodForOdd[-1] = True
    goodForEven = [False] * len(A)
    goodForEven[-1] = True
    ans = 1
        
    for i in range(len(A)-2, -1, -1):
        if even[i] > 0  and goodForEven[even[i]]:
            goodForOdd[i] = True
        if odd[i] > 0 and goodForOdd[odd[i]]:
            ans += 1
            goodForEven[i] = True
                
    return ans

计算odd和even有多种方法，比如从后往前维护一棵BST，找到A[i]对应的odd[i]和even[i]，再插入A[i] 还有一种单调栈（Monotonic Stack）的方法

def findNext(S):
    stack = []
    nextJ = [-1] * len(A)
    for j in S:
        while stack and stack[-1] < j:
            nextJ[stack[-1]] = j
            stack.pop()
        stack.append(j)
    return nextJ
        
s = sorted(range(len(A)), key = lambda x: A[x])
odd = findNext(s)
s = sorted(range(len(A)), key = lambda x: -A[x])
even = findNext(s)

S中是数组下标（按照A[x]从小到大排序），因此在findNext中，新循环到的值必然大于等于stack中的值 从栈顶弹出所有小于j的下标，将它们都指向j，然后把j压入栈 （弹出操作可以保证栈中从栈底到栈顶的index值是递减的，否则早就被弹出了）