[Data Structure] Monotonic Stack

Monotonic Stack이라는 구조에 대해 알아봅시다.

오늘 LeetCode의 Daily Question이 Monotonic Stack을 활용하는 문제이기 때문에 제대로 한번 알아보려고 합니다.

 

특징

Monotonic의 사전적 의미를 찾아봅시다.

출처: 네이버 사전

단조로운 Stack? 무슨 의미일까요?

2번 의미처럼 값이 증가 혹은 감소하는 단방향 변화만 존재하는 Stack을 의미합니다.

// General Stack
Bottom [4,3,12,5,6,1,31,7,13] Top

// Monotonic Increasing Stack
Bottom [1,3,4,5,6,7,12,13,31] Top

// Monotonic Decreasing Stack
Bottom [31,13,12,7,6,5,4,3,1] Top

 

그럼 Stack에 값을 추가할 때마다 정렬을 해줘야하는 걸까요? 그렇지 않습니다.

Monotonic Stack은 일반적인 Stack와 다르게 새로운 Push, Pop 규칙을 갖습니다.

 

Push

증가 혹은 감소의 규칙이 성립될 때만 Push가 이뤄집니다.

// Monotonic Increasing Stack
Bottom [1, 3] Top
Push 5 -> Bottom [1, 3, 5] Top : 조건 성립! Push 가능
Push 4 -> Bottom [1, 3, 5, 4] Top : 증가 조건 성립 안됨! Push 불가

// Monotonic Decreasing Stack
Bottom [14, 9] Top
Push 5 -> Bottom [14, 9, 5] Top : 조건 성립! Push 가능
Push 15 -> Bottom [14, 9, 5, 15] Top : 감소 조건 성립 안됨! Push 불가

 

Push가 불가하다면 값은 그냥 사라질까요?

만약 새로운 값이 증가 혹은 감소 조건을 깬다면 Pop이 작동하게 됩니다.

Push 불가로 인한 Pop

바로 Push 이후 증가 혹은 감소 조건이 만족될 때까지 Pop이 이뤄집니다.

// Monotonic Increasing Stack
Bottom [1, 3] Top
Push 5 -> Bottom [1, 3, 5] Top : 조건 성립! Push 가능
Push 4 -> Bottom [1, 3, 5, 4] Top : 증가 조건 성립 안됨! Push 불가

Push 4 보류
Pop -> Bottom [1, 3] Top, Pop Value: 5
Push 4 재시도 -> Bottom [1, 3, 4] Top : 조건 성립! Push 가능

 

Monotonic Decreasing Stack의 경우 15가 Push되기 위해서는 어떻게 해야할까요?

Stack의 모든 요소가 Pop 되고 나서야 Push가 가능해집니다.

구현

한번 구현해봅시다.

class MonotonicStack<T: Comparable> {
    enum MonotonicType {
        case increasing
        case decreasing
        
        var compare: ((T, T) -> Bool) {
            switch self {
            case .increasing: return (>=)
            case .decreasing: return (<=)
            }
        }
    }
    
    let type: MonotonicType
    var stack: [T] = []
    
    init(type: MonotonicType) {
        self.type = type
    }
}

 

먼저 MonotonicType과 비교기준을 정의해줍니다.

// in MonotonicStack class
func push(value: T) -> [T] {
    if stack.isEmpty {
        stack.append(value)
        return []
    }
    var temp: [T] = []
    // 조건에 만족할 때까지 pop
    while !stack.isEmpty {
        if type.compare(value, stack.last!) {
            break
        }
        temp.append(pop()!)
    }
    stack.append(value)
    return temp
}

func pop() -> T? {
    stack.popLast()
}

 

pop()은 일반적인 Stack과 동일하지만, push()는 조건에 맞는 상황이 될 때까지 pop하는 로직이 추가되었습니다.

 

테스트

let monotoniIncreasingStack = MonotonicStack<Int>(type: .increasing)
print(monotoniIncreasingStack.push(value: 1)) // [], Stack: [1]
print(monotoniIncreasingStack.push(value: 3)) // [], Stack: [1, 3]
print(monotoniIncreasingStack.push(value: 5)) // [], Stack: [1, 3, 5]
print(monotoniIncreasingStack.push(value: 4)) // [5], Stack: [1, 3, 4]
print(monotoniIncreasingStack.stack) // [1, 3, 4]

let monotoniDecreasingStack = MonotonicStack<Int>(type: .decreasing)
print(monotoniDecreasingStack.push(value: 14)) // [], Stack: [14]
print(monotoniDecreasingStack.push(value: 9))  // [], Stack: [14, 9]
print(monotoniDecreasingStack.push(value: 5))  // [], Stack: [14, 9, 5]
print(monotoniDecreasingStack.push(value: 15)) // [5, 9, 14], Stack: [15]
print(monotoniDecreasingStack.stack) // [15]

정상적으로 작동합니다.

활용 및 예제

Monotonic Stack은 주로 배열 안에서 특정 조건을 만족하는 가장 가까운 값을 찾는 문제에서 활용됩니다.

이제 LeetCode Daily Question을 풀어봅시다.

https://leetcode.com/problems/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.

Example 1:
    Input: nums = [6,0,8,2,1,5]
    Output: 4
    Explanation: The maximum width ramp is achieved at (i, j) = (1, 5): nums[1] = 0 and nums[5] = 5.

Example 2:
    Input: nums = [9,8,1,0,1,9,4,0,4,1]
    Output: 7
    Explanation: The maximum width ramp is achieved at (i, j) = (2, 9): nums[2] = 1 and nums[9] = 1.
    
Constraints:
    2 <= nums.length <= 5 * 10^4
    0 <= nums[i] <= 5 * 10^4

 

Monotonic Stack의 원리가 어떻게 활용될까요?

먼저 가장 앞의 값을 기준으로 Decreasing Stack을 생성해줍니다.

값이 아닌 Index를 저장하고, 조건에 맞지 않을 때는 기존 값들을 pop하는 것이 아니고 그냥 무시합니다.

var monotonicDecreasingStack: [Int] = [0]
for i in (0..<nums.count) {
    if nums[monotonicDecreasingStack.last!] > nums[i] {
        monotonicDecreasingStack.append(i)
    }
    // 값의 최솟값이 0이기 때문에 0이 나오면 반복 종료
    if nums[i] == 0 { break }
}

 

그리고 가장 뒤의 값부터 비교하며 거리의 최댓값을 저장합니다.

var result = 0
var count = nums.count - 1
// stack이 비었거나, 배열을 모두 돌면 종료
while !monotonicDecreasingStack.isEmpty && count > 0 {
    while let last = monotonicDecreasingStack.last, nums[last] <= nums[count] {
        // 최댓값 저장
        result = max(result, count - last)
        // 사용한 Index Pop
        _ = monotonicDecreasingStack.popLast()
    }
    count -= 1
}
return result

 

최종 코드

class Solution {
    func maxWidthRamp(_ nums: [Int]) -> Int {
        var monotonicDecreasingStack: [Int] = [0]
        for i in (0..<nums.count) {
            if nums[monotonicDecreasingStack.last!] > nums[i] {
                monotonicDecreasingStack.append(i)
            }
            if nums[i] == 0 { break }
        }
        print(monotonicDecreasingStack)
        var result = 0
        var count = nums.count - 1
		while !monotonicDecreasingStack.isEmpty && count > 0 {
            while let last = monotonicDecreasingStack.last, nums[last] <= nums[count] {
                result = max(result, count - last)
                _ = monotonicDecreasingStack.popLast()
            }
            count -= 1
        }
        return result
    }
}

Conclusion

Monotonic Stack의 기본 시간 복잡도는 O(n)이기 때문에 특정 조건에서 단순 반복문을 사용하는 것보다 더 짧은 시간으로 문제를 해결할 수도 있습니다.

Reference

https://www.geeksforgeeks.org/introduction-to-monotonic-stack-2