如何在O(N)时间复杂度下查找数组每个元素右侧大于等于自身的最右索引

针对无特殊约束的通用整数数组场景，不存在O(N)时间复杂度的解法，目前可实现的最优时间复杂度为O(NlogN)，即你已经实现的单调栈配合二分查找的方案。

单调栈确实能解决很多数组区间最值类问题，且这类可实现O(N)复杂度的问题，本质上都可以通过单调栈的单次栈顶比较直接得到答案，无需额外查找，比如「下一个更大元素」类问题只需要找最近的符合条件的元素，栈顶元素直接就是结果。
但本问题要求的是最右侧的符合条件的元素，该特性决定了无法仅通过栈顶单次比较得到结果，必须对栈中维护的有序候选序列做查找操作，而有序序列的查找最低时间复杂度为O(logN)，叠加N次遍历后整体复杂度为O(NlogN)。

你给出的实现逻辑正确，核心思路如下：

• 倒序遍历数组，维护一个严格单调递减的栈，栈中存储索引，索引对应的元素值严格递减
• 倒序遍历时，只有当前元素比栈顶索引对应的元素更大时才入栈，保证栈中元素越靠栈顶索引越靠左、对应值越小，整个栈的元素值保持严格单调递减
• 对每个遍历到的元素nums[i]，栈中存储的都是i右侧的候选索引，由于栈值单调递减，可通过二分查找直接找到第一个大于等于nums[i]的元素对应的索引，也就是最右侧的符合要求的j

对应的Python实现如下：

import bisect

def rightmostGreaterOrEqual(nums):
    A, n = nums, len(nums)    
    indx = [-1]*n 
    stack, stackv = [], []
    for i in range(n-1, -1, -1):
        if not stack or nums[stack[-1]] < nums[i]:
            stack.append(i) 
            stackv.append(nums[i])
        else:
            idx = bisect.bisect_left(stackv, nums[i])
            indx[i] = stack[idx]
    return indx

# 测试用例
B = [9,8,1,0,1,9,4,0,4,1]
rightGreat = rightmostGreaterOrEqual(B)
print(B)
# 输出: [9, 8, 1, 0, 1, 9, 4, 0, 4, 1]
print(rightGreat)
# 输出: [5, 5, 9, 9, 9, -1, 8, 9, -1, -1]

如果你的输入数组存在特殊约束，比如元素取值范围很小（例如限定在1~100区间），可以用后缀最大值计数的方式实现O(N + K)的时间复杂度，其中K为元素取值范围大小，但该方案仅适用于特定场景，不具备通用性。

内容的提问来源于stack exchange，提问作者bssrdf