프로그래머스-주식가격

https://programmers.co.kr/learn/courses/30/lessons/42584

이중 for문으로 모든 pair를 비교하면 O(n^2)이지만 stack을 활용하면 O(n)이다.
monotonic stack 문제는 오름/내림차를 결정하는게 제일 중요한데
여기서는 숫자가 줄어드는 순간 답이 하나씩 나오므로(예를 들어 1 2 3 다음에 2가 나오면 3은 1초 후에 줄어든단걸 알 수 있다) 오름차로 유지하면 된다.

새 원소를 push 해서 오름차가 깨진다면 깨지지 않을만큼 top을 pop하고,
더이상 push할게 없으면 남은건 다 pop 한다.

for 속에 while이 있어서 O(n^2)처럼 보이지만 모든 원소는 한번씩 push되고 한번씩 pop 되므로 O(n)이다.

원래는 지문이 안테나 어쩌고였는데 어느새 주식으로 바뀌었네...

import java.util.Stack;

class Solution {
    public int[] solution(int[] prices) {
        int[] answer = new int[prices.length];
        Stack<Integer> s = new Stack<>();
        for (int i=0; i<prices.length; ++i) {
            while (!s.empty() && prices[s.peek()] > prices[i]) {
                int top = s.pop();
                answer[top] = i - top;
            }
            s.push(i);
        }
        while (!s.empty()) {
            int top = s.pop();
            answer[top] = prices.length - 1 - top;
        }
        return answer;
    }
}