[アルゴリズムクイズ]プログラマのデュアル・ユーティリティ・プリアンブル・キュー

今日の問題はプログラマーの高得点kit hip分類のlevel 3問題です!( 質問リンク )
お尻の分類もカットされました.少なくとも今週中には終わります!

問題の説明

デュアル・ユーティリティ・プリアンブル・キューとは、次の演算が可能なデータ構造です.
コマンド受信タワー(高さ)Iのデジタルキューに指定した数字を挿入します.D 1キューから最値を削除します.D-1キューから最大値を削除します.
パラメータとして2つの優先順位キューで実行する演算操作を指定した場合、すべての演算を処理した後、キューが空の場合[0,0]空でない場合、「最値、最上昇値」を返すソルバを実装します.

せいげんじょうけん

操作は、100000より長い文字列配列である.

操作の要素は、キューが実行する操作を表す.

要素はコマンドデータ形式で提供されます.最大値/最大値を削除する操作で複数の最大値/最大値がある場合は、1つだけ削除します.

空のキューでデータの削除が要求された場合、この操作は無視されます.

I/O例

operationsreturn["I 16","D 1"][0,0]["I 7","I 5","I -5","D -1"][7,5]

解答方法

最初は最大と最小の数を知らなければならないので、pqと最大または最小の値を格納する変数にはなりませんか?removeがあるから?私は考えて、しかし除いて、二度と小数と大きい数を探し当てることができません!
したがって、削除後、次の大きい、小さいことを知るために、昇順で並べ替えられたpq、降順で並べ替えられたpqが宣言されます.
また、サイズが0の場合は演算を必要とせず、最終サイズが0の場合は値が異なる必要がありますが、2つのキューが使用されるため、countという変数を使用して実際の要素の個数を格納します.
operation stringを区切り記号として「」に分割し、これらの値を使用して演算のタイプを理解します.

挿入演算の場合、min、max優先キューはいずれも付与され、要素数が増加する.

アンインストール操作の場合、

要素の個数が0であれば、演算をスキップしたり、-演算があるかどうかを確認したりします.

-接着した場合、minから1つを除去します.そうしないとmaxから1つを除去した後、元素の数も減少します.

最初に結果配列に[0,0]を入れるため、最終要素の個数が0でない場合、maxとminから優先度の高い要素をそれぞれ取り出し、配列に入れて返す.

｢問題が発生する｣

このコードで答えを提出しましたが、最初のテストケースで問題が発生しました.さまざまなテストケースを考慮して問題を理解した結果、次のような問題が見つかりました.
上のコードでは、2つのキューに共通する要素がソートされます.ただし、要素を除去して要素の個数を0にしてから要素を挿入すると、実際には除去されていますが、残りの要素は順序を破壊します.(以下の場合)

したがって、削除操作が発生した場合、削除後、要素数が0の場合、追加コードは2つのキューをクリアします.

コード#コード#

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {0, 0};
        PriorityQueue<Integer> min = new PriorityQueue<>();
        PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
        String[] splited;
        int count = 0;
        for(String operation : operations){
            splited = operation.split(" ");
            switch (splited[0]){
                case "I" : {
                    max.add(Integer.valueOf(splited[1]));
                    min.add(Integer.valueOf(splited[1]));
                    count ++;
                    break;
                }
                case "D" : {
                    if(count == 0) continue;
                    if(splited[1].charAt(0) == '-') min.poll();
                    else max.poll();
                    count--;
                    if(count == 0){
                        min.clear();
                        max.clear();
                    }
                    break;
                }
            }
        }
        if(count != 0){
            answer[0] = max.poll();
            answer[1] = min.poll();
        }
        return answer;
    }
}