Javaスライドウィンドウの最大値の実現
2845 ワード
一、テーマ
整数配列numsをあげます。kサイズのスライドウィンドウがあります。配列の一番左から配列の一番右側に移動します。スライドウィンドウの中にあるk個の数字しか見えません。スライドウィンドウは1つずつ右に移動します。
スライドウィンドウの最大値を返します。
二、単調行列解析
テーマはスライドウィンドウのスライドを求め、ウィンドウのカバー範囲の最大値を返します。
この問題は優先順位の列には適していません。大きな屋根を使ってk個の数字を保管するので、この時の最大値は分かりますが、窓はスライドしています。一番上の山は毎回最大値だけをイジェクトできます。他の値は削除できません。つまり、スライドウィンドウの中の値は大きな山で維持できません。
だから、キューのメンテナンスを採用して、ウィンドウの移動につれて、列が先に出ます。
この時のキューに対する要求は、キューのトップが最大値で、全体の列が減少しています。
例えば、1,3,-1,-3,3,6,7
初期:1,3,-1,列は3,-1に預け入れて、それを減量させて、しかも最初はこの時のスライドウィンドウの最大値です。
-3に移動します。列:3、-1、-3
5に移動します。キュー:5
3に移動します。キュー:5、3
6に移動します。キュー:6
7に移動します。キュー:7
要求を満たすためには、カスタムキューが必要です。
例から分かるように、キューはウィンドウ内のすべての要素を維持する必要はなく、キューの最初のこの時点でウィンドウの最大を保証するだけでなく、キューの要素は減少し、コードを具体的に見てください。
三、コード
この問題は単調な列を利用して、自分でチームに入る規則を定義しなければなりません。
入隊:隊列の最初の要素を常に最大に保つと同時に、隊列内のメンテナンスウィンドウの大きさの要素が徐々に減少します。
チームを出る:現在の元素がチームに入るかどうかを判断し、チーム内で、また窓のスライドに従ってチームの操作を実行します。
ここで、Javaスライドウィンドウの最大値を実現するための文章を紹介します。Javaスライドウィンドウの最大値については、以前の文章を検索したり、下記の関連記事を見たりしてください。これからもよろしくお願いします。
整数配列numsをあげます。kサイズのスライドウィンドウがあります。配列の一番左から配列の一番右側に移動します。スライドウィンドウの中にあるk個の数字しか見えません。スライドウィンドウは1つずつ右に移動します。
スライドウィンドウの最大値を返します。
二、単調行列解析
テーマはスライドウィンドウのスライドを求め、ウィンドウのカバー範囲の最大値を返します。
この問題は優先順位の列には適していません。大きな屋根を使ってk個の数字を保管するので、この時の最大値は分かりますが、窓はスライドしています。一番上の山は毎回最大値だけをイジェクトできます。他の値は削除できません。つまり、スライドウィンドウの中の値は大きな山で維持できません。
だから、キューのメンテナンスを採用して、ウィンドウの移動につれて、列が先に出ます。
この時のキューに対する要求は、キューのトップが最大値で、全体の列が減少しています。
例えば、1,3,-1,-3,3,6,7
初期:1,3,-1,列は3,-1に預け入れて、それを減量させて、しかも最初はこの時のスライドウィンドウの最大値です。
-3に移動します。列:3、-1、-3
5に移動します。キュー:5
3に移動します。キュー:5、3
6に移動します。キュー:6
7に移動します。キュー:7
要求を満たすためには、カスタムキューが必要です。
例から分かるように、キューはウィンドウ内のすべての要素を維持する必要はなく、キューの最初のこの時点でウィンドウの最大を保証するだけでなく、キューの要素は減少し、コードを具体的に見てください。
三、コード
import java.util.Deque;
import java.util.LinkedList;
//
class MyQueue {
Deque<Integer> deque = new LinkedList<>();
// , ,
//
void poll(int val) {
if (!deque.isEmpty() && val == deque.peek()) {
deque.poll();
}
}
// , ,
//
// 3,1,2 , 1 , 1 , :3,2
void add(int val) {
while (!deque.isEmpty() && val > deque.getLast()) {
deque.removeLast();
}
deque.add(val);
}
//
int peek() {
return deque.peek();
}
}
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length == 1) {
return nums;
}
int len = nums.length - k + 1;
//
int[] res = new int[len];
int num = 0;
//
MyQueue myQueue = new MyQueue();
// k
for (int i = 0; i < k; i++) {
myQueue.add(nums[i]);
}
res[num++] = myQueue.peek();
for (int i = k; i < nums.length; i++) {
// ,
myQueue.poll(nums[i - k]);
//
myQueue.add(nums[i]);
//
res[num++] = myQueue.peek();
}
return res;
}
}
四、まとめこの問題は単調な列を利用して、自分でチームに入る規則を定義しなければなりません。
入隊:隊列の最初の要素を常に最大に保つと同時に、隊列内のメンテナンスウィンドウの大きさの要素が徐々に減少します。
チームを出る:現在の元素がチームに入るかどうかを判断し、チーム内で、また窓のスライドに従ってチームの操作を実行します。
ここで、Javaスライドウィンドウの最大値を実現するための文章を紹介します。Javaスライドウィンドウの最大値については、以前の文章を検索したり、下記の関連記事を見たりしてください。これからもよろしくお願いします。