単調スタックと単調キュー

単調スタックと単調キュー



Monotonic Stack Monotone Queue



著作権表示：この記事は、CC 4.0BY-SA著作権表示に準拠したCSDNブロガー「Alex_McAvoy」のオリジナル記事です。転載の際は、元のソースリンクとこのステートメントを添付してください。
元のリンク：https：//blog.csdn.net/u011815404/article/details/86896303

目次

1.原則

単調キューは、チームの最初から最後まで単調性を満たすキューです。単調なスタックと非常によく似ています。基本的な原理は単調なスタックと同じです。単調スタックの先入れ先出しプロパティを変更するだけです。



単調に増加するキューの場合、キューが空であるかエンキューされている場合x xテール要素以上の場合はキューに入れられます。そうでない場合、キューに入れるとキューの単調さが失われるため、テール要素をエンキュー要素と比較する必要があります。x xすべての大きな要素がチームを去ります。

単調に減少するキューの場合、キューが空であるかエンキューされている場合x xテール要素以下の場合、チームに参加します。そうでない場合、キューはキューの単調さを破壊するため、テール要素をキュー要素と比較する必要があります。x xすべての小さな要素がチームを去ります。



2.アプリケーション

単調なキューの一般的なアプリケーションは次のとおりです。

  1. 一連の数字が与えられたら、最初の大きい/小さい数字を見つけますx xの数
  2. 単調性を維持して、区間内の最小/最大の問題を解決します
  3. スライディングウィンドウの問題を解決する
  4. 最適化されたマルチバックパックDP、スロープ最適化DP

3.実現する

単調なキューは通常、STLの両端キュー（デュアルエンドキュー）を使用して実装されます。両端キューはキューの先頭とキューの最後で操作できるため、この性質により、キューの最後でのみ操作できる単調なスタックの不足が補われます。 、最初の段落に特定の制限があるようにします。

1）単調に増加するキュー

deque<int> Q //Double-ended queue for(int i = 1 i <= n i++) { //When the queue is not empty and the tail element is greater than the queue element while((!Q.empty()) && Q.back()>A[i]) { Q.pop_back() //Dequeue the elements at the end of the queue that are larger than the enqueue elements ... //Update result } q.push_back(A[i]) //Elements join the team ... //Update result }

2）単調に減少するキュー

deque<int> Q //Double-ended queue for(int i = 1 i <= n i++) { //When the queue is not empty and the tail element is less than the queue element while((!Q.empty()) && Q.back()<A[i]) { Q.pop_back() //Dequeue the element whose end of the queue is smaller than the enqueue element ... //Update result } q.push_back(A[i]) //Elements join the team ... //Update result }