動機

  • 我們要搜尋，所以一個要上升一個要下降
  • lis與一個要上升一個要下降的關係是?

Problem

A ramp in an integer array nums is a pair (i, j) for which i < j and nums[i] <= nums[j]. The width of such a ramp is j - i.

Given an integer array nums, return the maximum width of a ramp in nums. If there is no ramp in nums, return 0.

 

Example 1:

Input: nums = [6,0,8,2,1,5]Output: 4Explanation: The maximum width ramp is achieved at (i, j) = (1, 5): nums[1] = 0 and nums[5] = 5.

Example 2:

Input: nums = [9,8,1,0,1,9,4,0,4,1]Output: 7Explanation: The maximum width ramp is achieved at (i, j) = (2, 9): nums[2] = 1 and nums[9] = 1.

 

Constraints:

  • 2 <= nums.length <= 5 * 104
  • 0 <= nums[i] <= 5 * 104

Sol

有構成ramp有兩個條件

  • i < j
  • nums[i] <= nums[j]

而現在我們要搜尋，所以一個要上升一個要下降，很像two pointer的2 sum

class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        stk = []
        # index increasing, val decreasing
        for i in range(len(nums)):
            if not stk or nums[stk[-1]] > nums[i]:
                stk += i,
        
        ret = 0
        for i in range(len(nums)-1,-1,-1):
            while stk and nums[stk[-1]] <= nums[i]:
                ret = max(ret, i-stk.pop())
        return ret

也可以做lis

class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        stk = []
        
        ret = 0
        for i in range(len(nums)-1,-1,-1):
            n = nums[i]
            # index decreasing, val increasing
            if not stk or stk[-1][0] < n:
                stk += [n,i],
            else:
                j = stk[bisect.bisect(stk,[n,i])][1]
                ret = max(ret, j-i)
        return ret