株価

10051 ワード
Java programmers テキストリンク 
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;
    }
}
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;
    }
}
コード原則:一致した思考(深さの一致)
django 010 | Media