962. Maximum Width Ramp

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        """ tc O(NlgN) sc O(1)
        1. build decreasing mono stack : 
                (1)if current val is smaller than stack top || stack is empty, push into stack
                (2) otherwise, for current value A[j], find the first number that smaller than A[j]
                (3) update result 
        3. return res after loop ends
        
        note, why we build strictly decresing instead of non-increasing?    we want to get max diff so  if value is the same, we only keep the one appears first 
        """
        res = 0
        n = len(A)
        st = []
        for j in range(n):
            if not st or st[-1][0] > A[j]:
                st.append([A[j],j])
            else:
                left, right = 0, len(st)
                while left < right:
                    mid = left + (right-left)//2
                    if st[mid][0] > A[j]:
                        left = mid + 1 
                    else:
                        right = mid 
                i = st[left][1]
                res = max(res,j-i)
        return res 
############################################or #####################
        res = 0
        n = len(A)
        st = []
        for i in range(n)[::-1]: # range(n-1,-1,-1)
            if not st or st[-1][0] < A[i]: # from end to start to get a mono increasing stack, cache index so its index is not changed 
                st.append([A[i],i])
            else:
                j = st[bisect.bisect(st,[A[i],i])][1]
                res = max(res,j-i)
        return res 

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        """ tc O(N) sc O(1)
        1. build strictly decreasing mono stack 
        2. start from idex n-1 to 0, if stack top st[-1]<= A[i],  (1)update the result (2) pop off stack 
        3. return res after loop ends
        
        note, why we build strictly decresing instead of non-increasing?    we want to get max diff so  if value is the same, we only keep the one appears first 
        """
        n = len(A)
        st = []
        for i in range(n):
            if not st or A[st[-1]] > A[i]:
                st.append(i)

        res = 0
        for j in range(n-1,-1,-1):
            while st and A[st[-1]] <= A[j]:
                res = max(res, j-st[-1])
                st.pop()
        return res 

class Solution:
    def maxWidthRamp(self, A: List[int]) -> int:
        """ tc O(NlgN) sc O(1)
        main idea: greedy -  create (value,index) tuple, sort by value,  two pointer to track strictly increasing idx of A[left] and A[right], otherwise, jump left ptr to right, move right one step more   
        """
        n = len(A)
        val_i = [(v,i) for i, v in enumerate(A)]
        val_i = sorted(val_i)
        #print(val_i)
        res = 0
        st = []
        left = 0 
        right = 1
        while right < n:
            while right < n and  val_i[right][1] > val_i[left][1]:
                res = max(res,val_i[right][1]- val_i[left][1])
                right += 1
            if right < n :
                left = right
                right = right + 1
        return res