주식가격

import java.util.*;


public class 주식가격 {
    public Queue<Integer> solution(int[] prices) {
  
        Queue<Integer> q = new LinkedList<>();
        
        for(int i=0; i<prices.length; i++){
            int cnt = 0;
            for(int j=i+1; j<prices.length; j++){
                if(prices[j] >= prices[i]){
                    cnt++;
                }else{
                    cnt++;
                    break;
                }
               
            }
             q.offer(cnt);
        }
        return q;
    }
}

큐를 사용하긴 했지만 삽입할 때만 자료형을 쓰며, 시간 복잡도가 n^2 이 나왔다.
시간 복잡도를 줄이기 위해 stack 자료형을 사용하여 문제를 다시 풀었다 위의 방식대로 하여도 효율성 테스트까지는 통과했다.

import java.util.*;

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]){                
                answer[s.peek()] = i - s.peek();
                s.pop();
            }           
            s.push(i);    
        }
        
        while(!s.empty()){
            answer[s.peek()] = prices.length-s.peek()-1;
            s.pop();
        }
        
        return answer;
    }
}