Problem statement

https://binarysearch.com/problems/View-Over-People/

Solution

Use monotonic deque to find for each index i index with not smaller number. Then check if it is far enough.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums, k):
        stack, n = [], len(nums)
        result, ans = [-1]*n, []
        
        for i, num in enumerate(nums):
            while stack and stack[-1][1] <= num:
                a, b = stack.pop()
                result[a] = i
            stack.append((i, num))

        for i in range(n):
            if result[i] > i + k or result[i] == -1:
                ans += [i]

        return ans