Monotonic Stack(단조 스택) 간단 정리 및 활용

Monotonic Stack(단조 스택)

• 단조 스택

  기존의 스택을 모든 원소들이 오름차순이나 내림차순으로 단조롭게 하는 것

  기존 원소들 중 특정 원소를 제거하여 정렬하는 방식

• 활용

  • 문제 봉착

    LeetCode 901. Online Stock Span 을 풀던 중 문제 발생
    
    ```
    
    class StockSpanner:
    
        def __init__(self):
            self.prices = []
    
            self.count = 0
    
        def next(self, price: int) -> int:
            result = 1
    
            # 1. 스택을 복사함
            stack = self.prices[:]
    
            while stack and stack[-1] <= price:
                result += 1
                stack.pop()
    
            self.count += 1
            self.prices.append(price)
    ```
    
    해당 코드에서는 next 가 호출될 때 마다 price 에서 stack 으로 값을 복사함
    
    호출될 때 마다 복사하는 절차를 거치다보니 time exceed 발생
    

  • 문제 해결 실패

    ```
    
    class StockSpanner:
    
        def __init__(self):
            self.prices = []
            # 캐싱용 table 생성
            self.table = {}
            self.count = 0
    
        def next(self, price: int) -> int:
            result = 1
    
            if price in self.table:
                return self.table[price]
    
            # 1. 스택을 복사함
            stack = self.prices[:]
    
            while stack and stack[-1] <= price:
                result += 1
                stack.pop()
    
            self.count += 1
            # 호출될 때 마다 price 의 result 값이 저장됨
            self.table[price] = result
            self.prices.append(price)
    ```
    
    DP 처럼 캐싱을 해서 시간을 절약해보자. 라고 생각했지만 해당 코드처럼 table 에 값을 저렇게 저장하면 prices 가 [90, 90, 90] 같은 형태로 올 경우 의미가 없어짐
    

  • Monotonic Stack 을 활용한 문제 해결

    
        class StockSpanner:
    
            def __init__(self):
                self.monotone_stack = []
    
            # 100, 80, 60, 70, 60, 75, 85
            def next(self, price: int) -> int:
                # [(100, 1),(80, 1), (60, 1)]
                # [(100, 1), (80, 1), (70, 2)]
                # [(100, 1), (80, 1), (70, 2), (60, 1)]
                # [(100, 1), (80, 1), (75, 4)]
                # [(100, 1), (85, 6)]
                stack = self.monotone_stack
    
                cur_price_quote, cur_price_span = price, 1
    
                while stack and stack[-1][0] <= cur_price_quote:
                    prev_price_quote, prev_price_span = stack.pop()
    
                    cur_price_span += prev_price_span
    
                stack.append((cur_price_quote, cur_price_span))
    
                return cur_price_span
    
    

    monotonic stack 을 이용해 stack 자체를 단순히 함

    stack 은 단순해지지만 span 값은 stack 내부의 자료구조에 저장되므로 stack 을 복사하지 않고 계속 사용할 수 있음