Leetcode 962. Maximum Width Ramp

문제

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.

• ramp(경사면) 은 정수 배열에서 인덱스 i, j 가 i < j 이면서 nums[i] <= nums[j] 인 (i, j) 쌍을 의미한다.
• 경사면의 길이는 j - i 로 표현될때, 주어진 정수 배열에서 가장 긴 경사면의 길이를 구하시오.

예시

[6,0,8,2,1,5]

• 1번 index (0) 과 5번 index (5) 가 가장 긴 경사로를 형성한다.
• 정답은 5 - 1, 4이다.

제한

• $2 <= nums.length <= 5 * 10^4$
• $0 <= nums[i] <= 5 * 10^4$

풀이

• 일단 먼저 배열의 값이 절대적으로 작아지는 모노토닉 스택을 만들고 안에 index를 저장해둔다.
  • 배열의 값이 커질경우 어차피 그 앞에 있는 값보다 경사면이 길어질수가 없다.
• 그 뒤, 뒤에서부터 순회하여 모노토닉 스택의 top과 경사면을 형성할경우, 그 길이로 정답을 재구성하고, 스택에서 뺀다.
  • 어차피 이 길이가 그 index가 왼쪽에 위치할때 최선의 길이이기에 빼도 된다.

class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        st = []

        for idx, num in enumerate(nums):
            if not st or nums[st[-1]] > num:
                st.append(idx)

        ans = 0

        for idx in range(len(nums) - 1, -1, -1):
            while st and nums[st[-1]] <= nums[idx]:
                ans = max(ans, idx - st[-1])
                st.pop()
            if not st:
                return ans

        return ans