[코테 연습] 962. Maximum Width Ramp

- 스택 / 단조스택 ( monototic stack ) / 배열문제

 

https://leetcode.com/problems/maximum-width-ramp/description/?envType=daily-question&envId=2024-10-10

 

- 문제분석

1. 양수의 숫자가 나열되어있는 nums 배열이 있다.

2. i < j  를 만족하며,  j - i 가 가장 크고, nums[i] 와 nums[j] 가 같거나 nums[j] 가 큰 숫자 중 너비 값이 가장 큰 ramp 를 구하라. 

 

- 문제풀이

1. Stack 을 선언하여 단조 감소 스택을 만든다. 

1-1. 단조 감소 스택을 구성한다는 의미는 Stack 에 저장된 값들이 항상 내림차순을 유지하도록 값을 삽입하는 것이다.

1-2. 즉, 스택에 들어가는 값들이 스택의 상단에서 하단으로 갈수록 작아지는 구조를 유지하는 것.

2. 단조 감소 스택을 만들기 위해서는 nums 의 배열을 반복문으로 처리하며, stack에 담겨 있는 값이 nums[i] 값 보다 커야한다.

 

• nums[stack.peek()] > nums[i]가 성립할 때만 i를 스택에 삽입합니다.
• 이렇게 하면, 스택 안에 있는 인덱스들은 모두 그에 해당하는 nums 배열 값들이 단조 감소하는 순서로 정렬됩니다. 즉, 스택에서 꺼낼 때는 항상 더 작은 값들이 먼저 나오게 됩니다.
• 예시:
  • int[] nums = {6, 0, 8, 2, 1, 5};  
  • 처음 배열을 순회하며 nums의 인덱스들을 스택에 넣을 때, 스택이 항상 단조 감소 순서를 유지하도록 삽입합니다:
    • i = 0, nums[0] = 6 -> 스택: [0]
    • i = 1, nums[1] = 0 -> nums[1] < nums[0] 이므로 삽입 -> 스택: [1, 0]
    • i = 2, nums[2] = 8 -> nums[2] > nums[1] 이므로 삽입하지 않음
    • i = 3, nums[3] = 2 -> nums[3] > nums[1] 이므로 삽입하지 않음
    • i = 4, nums[4] = 1 -> nums[4] < nums[3] 이므로 삽입 -> 스택: [4, 1, 0]
    • i = 5, nums[5] = 5 -> nums[5] > nums[4] 이므로 삽입하지 않음
    결과적으로, 스택은 [1, 0]의 인덱스를 유지하게 됩니다. 이는 각각의 nums[i] 값이 내림차순을 유지하는 인덱스들의 집합입니다.

3. nums 를 내림차순으로 반복하면서, nums[stack.peek()] <= nums[i] 의 조건을 만족하는 것을 확인하며 가장 큰 j - i 를 찾는다.

 

> java

 

class Solution {
    public int maxWidthRamp(int[] nums) {
        
        Deque<Integer> deque = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++) {
            //deque 가 비어있거나, deque 의 숫자가 nums[i] 의 숫자보다 큰 경우 deque 에 넣는다.
            // 이렇게 하면 deque 에는 nums[i] 보다 큰 숫자의 index 만 남아있게 된다.
            
            if (deque.isEmpty() || nums[deque.peek()] > nums[i]) {
                deque.push(i);
            }
        }

        int max = 0;
        for (int i = nums.length-1; i >= 0; i--) {
            // deque 를 pop() 했을 때, deque 에 있는 index의 값보다 작거나 큰 값을 max 로 정의하게된다.
            while (!deque.isEmpty() && nums[deque.peek()] <= nums[i]) {
                max = (int)Math.max(max, i - deque.pop());
            }
        }

        return max;
    }
}

 

 

 

> python

 

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

        for i in range(n) :
            j = n - 1 - i
            while arr and nums[arr[-1]] <= nums[j] :
                _max = max(_max, j - arr.pop())


        return _max