プログラマ-デュアル・ユーティリティ・プリアンブル・キュー

1.質問

質問リンク

2.解答

問題を解く方法は三つある.

1.優先キューの使用

この問題の問題のように,優先順位キューを用いて問題を解く方法を考えてみよう.
問題を解決するには、2つの優先キューが必要です.
1つは最小お尻の優先順位キューで、
一つは最大お尻で表現する優先順位Q
この2つのキューがある場合、データ挿入コマンドは2つのhipに挿入されます.
「最低価格の削除」コマンドは、最上位のキューからデータをポーリングします.
最小臀部優先キューから削除
「≪最高値の削除｜Delete Maximum｜emdw≫」コマンドは、データの最小優先キューをポーリングします.
最大臀部優先キューから削除すればいいです.
今残っているのは最小お尻と最大お尻の体現です.
JAVAベースの優先順位キューは最小ヒップを採用.
すなわち,ルートノードは最小値を保証する木である.
では、崔大臀は優先キューに入れるデータを記号に変えて入れればいいのではないでしょうか.
例えば、10を-10に入れる.
では、投票の時だけ記号を変えておけば、簡単に最大のお尻を実現できます.
完全なコード

import java.util.PriorityQueue;
import java.util.Queue;
class Solution {
    public int[] solution(String[] operations) {
   	Queue<Integer> minHeap = new PriorityQueue<>(); // 최소힙
	Queue<Integer> maxHeap = new PriorityQueue<>(); // 최대힙

	for (int i = 0; i < operations.length; i++) {
            // 데이터 삽입
	    if (operations[i].charAt(0) == 'I') { 
	        int data = Integer.parseInt(operations[i].split(" ")[1]);
		minHeap.add(data);
		maxHeap.add(-data); // 최대힙은 부호를 바꿔서 넣기
	    } 
            // 최대값 삭제
	    else if (!minHeap.isEmpty() && operations[i].equals("D 1")) { 
                // 서로 부호가 반대이므로 poll할 때 부호 전환
		minHeap.remove(-maxHeap.poll()); 
            }
            // 최소값 삭제
	    else if (!minHeap.isEmpty() && operations[i].equals("D -1")) { 
                // 서로 부호가 반대이므로 poll할 때 부호 전환
		maxHeap.remove(-minHeap.poll()); 
            }
	}
        
        // 최대힙은 poll할 때 부호를 원래 부호로 바꿔줌
	return minHeap.isEmpty() ? new int[] {0, 0} : new int[] {-maxHeap.poll(), minHeap.poll()};
    }
}

このメソッドでは、特定のデータのオブジェクトを削除する必要があります.
特定のオブジェクトを検索するにはo(N)の時間が必要であり、オブジェクトを削除するにはo(logn)の時間が必要である.
N回繰り返されるので,時間的複雑度は約o(n^2 logn)である.

2.利用ソート

1番の方法で解いても、優先順位を利用する価値は小さい.
これは,最終的な削除操作にO(Nlogn)の時間がかかるためである.
これは、高速または残りの時点の時間的複雑さと同じです.
もしそうなら、配列を宣言してデータを入れるだけです.
コマンドを削除するときのみソートします.
一番後ろの要素を削除すると、
最大値を削除する場合は、一番前の要素を削除してください.
問題では、必要なデュアル・ユーティリティ・プリアンブル・キューを実装します.
完全なコード

function solution(operations) {
    const pq = [];

    operations.forEach(operation => {
        let [cmd, num] = operation.split(' ');
        
        // 데이터 삽입
        if (cmd == 'I') {
            pq.push(Number(num));
        }
        // 데이터 삭제
        else if (pq.length) {
            // 정렬을 한 후에
            pq.sort((a, b) => a - b);
            
            // 최댓값 삭제일 때는 맨 뒤의 요소를,
            // 최솟값 삭제일 때는 맨 앞의 요소를 제거
            pq[num == 1 ? 'pop' : 'shift']();
        }
    });
    
    // 마지막으로 정렬한 후에 리턴
    pq.sort((a, b) => a - b);
    return pq.length ? [pq[pq.length - 1], pq[0]] : [0, 0];
}

このメソッドのソートにはo(Nlogn)時間がかかります.
最大値または最小値を削除するにはO(N)の時間が必要です.
N回繰り返すと、約o(n^3 logn)の時間がかかります.
結局、優先順位には勝てなかった.
削除にはO(N)時間が必要です.
配列をコピーする演算が入っているからです.
最長値を削除するにはo(1)の時間しかかかりません.
最大値を削除するには、1番インデックスから(size-1)番インデックスへのデータが必要です.
0番インデックスから(size-2)番インデックスにコピーする必要があります.
時間がかかる.

3.使用リスト

2番の方法とあまり違わない答え
2番の方法を見た人のうち何人かが推測したかもしれません
「並ばなきゃいけないの?」そうですね.
間違いない.ソートする必要がなく、最大値と最大値を見つけることができます.
もっと速く
0番インデックスから(size-1)番インデックスに線形にナビゲートします.
最低価格または最高価格のインデックスを見つけます.
インデックスに対応する要素をリストから削除します.
完全なコード

function solution(operations) {
    const pq = [];

    operations.forEach(operation => {
        let [cmd, num] = operation.split(' ');
        
        // 데이터 삽입
        if (cmd == 'I') {
            pq.push(Number(num));
        }
        // 데이터 삭제
        else if (pq.length) {
            const removeElem = Math[num == 1 ? 'max' : 'min'](...pq);
            const removeIndex = pq.findIndex(elem => elem == removeElem);
            pq.splice(removeIndex, 1);
        }
    });
      
    return pq.length ? [Math.max(...pq), Math.min(...pq)] : [0, 0];
}

この方法は最低価格や最高価格を探すのにo(N)の時間がかかる.
削除にはo(N)の時間が必要です.
これは全部でN回繰り返されるので、全部でo(n^3)の時間がかかります.