주식가격

• 스택에는 아직 감소하지 않은 주식가격들을 저장하고 있는 것이 기본적인 풀이법. 이렇게 하면 증가하는 순서로 스택이 유지된다. 흔히 쓰이는 테크닉이다.
• 시간 복잡도는 모든 원소를 한번씩 스택에 추가/삭제하므로 O(n)이 된다.
  • 그러나 다른 사람들의 풀이를 보면 O(nm)의 코드들도 많이 상위에 올라가 있다..

"""Solution code for "Programmers 42584. 주식가격".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/42584
- Solution link: http://www.teferi.net/ps/problems/programmers/42584
"""


def solution(prices):
    answer = [None] * len(prices)
    stack = []
    for cur_time, cur_price in enumerate(prices):
        while stack and prices[stack[-1]] > cur_price:
            time = stack.pop()
            answer[time] = cur_time - time
        stack.append(cur_time)
    for time in stack:
        answer[time] = cur_time - time
    return answer