962. Maximum Width Ramp

Problem : https://leetcode.com/problems/maximum-width-ramp

 

Difficulty : Medium

 

Status : Solved

 

Time : 00:37:55

 

---

 

문제 설명

 

정수 배열 nums 내의 램프(ramp, 경사면)는 i < j이고 nums[i] <= nums[j]인 (i, j) 쌍이다. 이 램프의 너비는 j-i이다.

 

정수 배열 nums가 주어질 때 nums 내 램프 중 최대 너비를 구하여라. 만약 램프가 없다면 0을 반환하라.

---

 

풀이

 

풀면서 이게 맞나? 싶었다. 실제로도 시간 및 공간 효율이 하위 5%를 찍는 걸 보면... 더 나은 방식이 있을 것도 같다.

 

nums와 nums의 원래 인덱스를 정렬할텐데, 이 때 정렬 기준은 (숫자의 크기 내림차순, 원래 인덱스 내림차순)이 된다.

이제 이 정렬된 nums를 탐색할텐데, 이 때 다음이 성립한다.

• 다음 nums는 이전 nums보다 크기가 작거나 같음이 무조건 보장된다.
• 따라서 현재 인덱스와, 이미 저장된 인덱스 중 제일 큰 값을 비교한다면...
  • 둘 사이의 차가 양수라면, 현재 원소가 왼쪽일 때의 가장 큰 램프 너비를 구할 수 있게 된다.

총 시간복잡도 O(nlogn) 내에 풀이 가능하다.

 

 

풀이 코드

class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        num = [(n, i) for i, n in enumerate(nums)]
        num.sort(key = lambda x : (-x[0], -x[1]))

        prev_max = 0
        result = 0
        for _, i in num :
            result = max(result, prev_max - i)
            prev_max = max(prev_max, i)

        return result