LeetCode [962]: Maximum Width Ramp

📌 LeetCode [962]: Maximum Width Ramp

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

---

문제 설명 📄

주어진 배열 nums에서 가장 긴 Ramp를 찾아야 합니다. Ramp는 두 인덱스 (i, j)에 대해 다음 조건을 만족합니다:

1. i < j
2. nums[i] <= nums[j]

목표는 가능한 Ramp 중 j - i를 최대화하는 값을 반환하는 것입니다.

---

문제 접근 방식

1. 스택 빌드:
   • 배열을 왼쪽에서 오른쪽으로 순회하면서, 작아지는 값의 인덱스만 스택에 추가합니다.
   • 스택에는 Ramp의 시작점이 될 가능성이 있는 인덱스만 남습니다.
2. 스택 활용:
   • 배열을 오른쪽에서 왼쪽으로 순회하면서, 스택의 값과 비교해 Ramp를 계산합니다.
   • 스택의 값이 조건을 만족하면 길이를 계산하고, 더 이상 조건을 만족하지 않는 값은 제거합니다.

---

Solution 💻

class Solution:
    def maxWidthRamp(self, nums: List[int]) -> int:
        stack = []
        for i in range(len(nums)):
            if not stack or nums[stack[-1]] > nums[i]:
                stack.append(i)

        answer = 0
        for j in range(len(nums) - 1, -1, -1):
            while stack and nums[stack[-1]] <= nums[j]:
                answer = max(answer, j - stack.pop())
        
        return answer

시간 복잡도 분석 ⏲️

• 스택 빌드: O(n)
  • 배열을 한 번 순회하며 단조 증가 스택을 만듭니다.
• 스택 활용: O(n)
  • 배열을 한 번 순회하며 스택과 비교합니다.
• 전체: O(n)

공간 복잡도 분석 🗄️

• 공간 복잡도: O(n)
  • 단조 증가 스택을 저장하는 데 사용됩니다.