962. Maximum Width Ramp (Medium) - TengnanYao/daily_leetcode GitHub Wiki

class Solution(object):
    def maxWidthRamp(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # O(n) stack
        s = [0]
        n, result = len(nums), 0
        for i in range(1, n):
            if nums[i] < nums[s[-1]]:
                s.append(i)
        for i in range(n - 1, -1, -1):
            while s and nums[i] >= nums[s[-1]]:
                result = max(result, i - s[-1])
                s.pop()
        return result
        
        # O(nlgn) mono stack + binary search
        monostack = [0]
        result = 0
        for i in range(1, len(nums)):
            num = nums[i]
            if num < nums[monostack[-1]]:
                monostack.append(i)
            else:
                l, r = 0, len(monostack) - 1
                while l <= r:
                    m = (l + r) // 2
                    val = nums[monostack[m]]
                    if num >= val:
                        r = m - 1
                    else:
                        l = m + 1
                result = max(result, i - monostack[l])
        return result
        
        # O(n^2) brute force two pointers TLE
        n = len(nums)
        result = -1
        for i in range(n):
            for j in range(n - 1, -1, -1):
                if nums[i] <= nums[j]:
                    result = max(result, j - i)
                    break
        return result