トピック分析
| 配列 nums が与えられたとき、配列の左端から右端に移動するサイズ k のスライディング・ウィンドウがあります。あなたが見ることができるのは、スライディングウィンドウ内のk個の数字だけです。スライディングウィンドウは一度に 1 桁ずつ右に移動します。スライディングウィンドウ内の最大値を返します。 |
配列 nums が与えられたとき、配列の左端から右端に移動するサイズ k のスライディング・ウィンドウがあります。あなたが見ることができるのは、スライディングウィンドウ内のk個の数字だけです。スライディング・ウィンドウは一度に1桁ずつ右に移動します。
スライディングウィンドウ内の最大値の配列を返します。
例
: nums = [1,3,-1,-3,5,3,6,7], そして= 3
: [3,3,5,5,6,7]
:
スライディングウィンドウの位置 最大
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
この問題はやや難しいです！熟読をお勧めします
授業が終わったら練習しましょう
トピック分析
この問題は、トピックのために多くの追加説明を必要とせず、直接理解し、分析する必要があります。それは暴力的な解決策を実施するために、各ウィンドウの最大値を見つけるために、すべてのスライディングウィンドウを介して横断することができ、考えるのは簡単です。それはどのように多くのスライディングウィンドウの合計は、小学校のトピックでは、 L-k + 1 ウィンドウの合計を得ることができます。
nums = [1,3,-1,-3,5,3,6,7]、k = 3とすると、ウィンドウの数は6です。
分析に基づいて、コードを完成させるのは簡単です：
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
if (len * k == 0) return new int[0];
int [] win = new int[len - k + 1];
//すべてのスライディングウインドウを反復する
for (int i = 0; i < len - k + 1; i++) {
int max = Integer.MIN_VALUE;
//各スライディングウィンドウの最大値を求める
for(int j = i; j < i + k; j++) {
max = Math.max(max, nums[j]);
}
win[i] = max;
}
return win;
}
}
走行結果
線形問題解決
ここでは販売していない、実際には、この質問は、より古典的な、あなたが解決するためにキュー、DP、ヒープや他の方法を使用することができます、すべてのアイデアの主なソースは、ウィンドウのスライディングの過程で、どのように速く最大値を見つけるプロセスを完了する必要があります。しかし、最も典型的な解決策は、やはりダブルエンドのキューを使用することです。具体的な解決方法は、一緒に見てみましょう。
まず、ダブルエンド・キューとは何かということを理解してください。ダブルエンド・キューは、キューとスタックの性質を持つデータ構造です。ダブルエンド・キューの要素は、どちらかの端からポップしたり挿入したりすることができます。
窓はダブルエンドのキューを使用して実装することができます。
そしてもう1つ、現在のウィンドウの最大値を維持するためにダブルエンド・キューの先頭に ** いる間だけその配列をトラバースし、トラバースの間中、各ウィンドウの最大値を結果配列に記録します。**最終的な結果配列は以下のようになります。
nums = [1,3,-1,-3,5,3,6,7]、k = 3とします。
この分析に基づき、コードが導き出されました：
func maxSlidingWindow(nums []int, k int) []int {
if len(nums) == 0 {
return []int{}
}
//スライスによるダブルエンド待ち行列のモデル化
queue := []int{}
result := []int{}
for i := range nums {
for i > 0 && (len(queue) > 0) && nums[i] > queue[len(queue)-1] {
//現在の要素より小さい要素を犠牲にする
queue = queue[:len(queue)-1]
}
//現在の要素をキューに入れる
queue = append(queue, nums[i])
if i >= k && nums[i-k] == queue[0] {
//キューを維持し、そのヘッダー要素が現在のウィンドウの最大値になるようにする
queue = queue[1:]
}
if i >= k-1 {
//結果を並べる
result = append(result, queue[0])
}
}
return result
}
実施結果：
パーファクト
私が書いたすべての解答と各問題の完全な図解をeBookにまとめました。
