[LeetCode] 962. Maximum Width Ramp

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

leetcode - Maximum Width Ramp

문제 유형 : 스택, 모노토닉 스택

문제 난이도 : Medium

 

문제

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.

 

정수 배열 nums의 ramp는 (i, j)쌍이 nums[i] <= nums[j]와 i < j를 만족하는 것을 말한다.

이 너비는 j-i이다.

정수 배열 nums가 주어지는데, 최대 ramp너비를 구하시오.

없으면 0을 반환하시오.

 

풀이

순차적으로 배열을 읽으면서, 스택에 인덱스를 저장한다.

스택에는 스택의 톱보다 더 큰 수의 인덱스만 저장시킨다.

 

역으로 배열을 읽으면서, nums[j]가 스택의 톱보다 크다면, 

최대 길이를 업데이트시킨다.

그러고 스택을 pop시키면서 계속 빼본다. 스택의 바닥일수록 왼쪽 인덱스에 가까워지므로, 범위를 늘려가며 시도하는 것이다.

만약 j가 i보다 작더라도 괜찮다. 값 갱신은 되지 않으므로.

 

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int maxWidthRamp(vector<int>& nums) {
        int n = nums.size();
        stack<int> s;
        
        for(int i = 0; i < n; ++i) {
            if(s.empty() || nums[s.top()] > nums[i]) {
                s.push(i);
            }
        }
        int maxRamp = 0;
        for(int j = n-1; j >= 0; --j) {
            while(!s.empty() && nums[s.top()] <= nums[j]) {
                maxRamp = max(maxRamp, j - s.top());
                s.pop();
            }
        }

        return maxRamp;
    }
};