もっと辛い(java)


問題の説明



考える

  • scovilleの長さは最大10,000,000であるため,最小値を直接検索するPriorityQueue最小hipを用いる.
  • 最小値がkより小さい場合は
  • を繰り返し、要素が1つ残っている場合は-1を返します.

    説明する

    import java.util.PriorityQueue;
    class Solution {
        public int solution(int[] scoville, int K) {
            int ans = 0;
            PriorityQueue<Integer> heap = new PriorityQueue<>();
            
            for( int i : scoville) heap.offer(i);
            
            while(heap.peek() < K){
                if(heap.size() == 1) return -1;
                
                int a = heap.poll();
                int b = heap.poll();
                int sum = a + ( b * 2 );
                heap.offer(sum);
                ans++;
            }
            return ans;
        }
    }
    
    これは、データ量が多く、その中から最小値を2つ抽出して追加する必要があるという問題であるため、優先順位キューを考慮する必要がある.
    Javaでは、PriorityQueueは、時間複雑度N(1)から最大N(LogN)までのバイナリツリーを使用します.
    PriorityQueueの機能を見てみましょう
    .peek()->最も優先度の高い要素を取得します.(追加された値は優先順位で並べ替えられます)
    要素を.prove()->queueに入れます.
    .poll()->優先度が最も高い要素を返します.
    .remove()->最も優先度の高い要素を削除します.
    .size()->queueのサイズを返します.
    これらの技能を利用して問題を解くなら、難しくない.