#データ構造とアルゴリズム学習ノート#剣指Offer 62:スライドウィンドウの最大値+オンライン処理(Java、C/C++)

2019.3.3《剣指Offer》零单刷个人笔记整理(66题全)目标传送门
この問題も効率的な問題で、文字列と配列は一般的にオンライン処理を考慮することができます.アルゴリズムプロセスについて説明します.
1.要素の下にあるダブルエンドキューリストと最終結果シーケンスresultを記録するために作成します.
以下、試験例について、配列{2,3,4,2,6,2,5,1}、スライドウィンドウサイズ3を入力し、アルゴリズム手順を説明する.
2.listを初期化し、初期ウィンドウの最後から2番目の要素kから1回の操作を実行します.行先からキュー内の要素kが小さいすべての要素を削除し、要素kの位置をキューの先頭に追加します(今回の操作を覚えておいてください.次にも使用します).
初期ウィンドウの要素は{2,3,4}であり、k=3以前のすべての要素を操作し、3が最大であるため、対応する下に1、最終list={1}と表示される.
3.最初のウィンドウ(最初のウィンドウの最後の要素)から、上記の操作を実行します.
最初のウィンドウの要素は{2,3,4}であり、k=4以前のすべての要素を操作し、4が最大であるため、対応する下に1、最終リスト={2}と表示される.
4.listキューテールの最大要素について、ウィンドウ範囲(キューヘッダ-キューテール+1?ウィンドウサイズ、一度チェックするだけ)を超えているかどうかをチェックし、超えている場合はキューテール要素を削除します.最大要素をresultに追加します.
ウィンドウが{3,4,2}に進むとlistの要素は{3,2}(キューヘッダは3,キューテールは最大2)となり,3−2+1<3をチェックし,要求に合致し,位置2対応要素4をresultに加える.
ウィンドウが{2,5,1}に進むとlistの要素は{7,6,4}(キューヘッダは7であり、6(対応数字5)は7(対応数字1)より小さくないので削除せず、キューヘッダは最大4(対応数字6))となり、キューヘッダ7-4+1>3をチェックし、数字6がウィンドウ範囲外であることを説明し、削除する.listは最終的に{7,6}であり、位置6対応要素5をresultに加える.
5.上記の操作3と検査4のプロセスを循環し、リストの最後の要素が最大になることを保証することができる.
タイトルの説明
配列とスライドウィンドウのサイズを指定し、すべてのスライドウィンドウの数値の最大値を見つけます.例えば、配列{2,3,4,2,6,2,5,1}およびスライドウィンドウのサイズ3を入力すると、合計6つのスライドウィンドウが存在し、それらの最大値はそれぞれ{4,4,6,6,6,6,5}である.配列{2,3,4,2,6,2,5,1}に対するスライド窓は,{[2,3,4],2,6,2,5,1},{3,4,2,5,1},{2,3,[4,2,6],2,5,1},{2,3,4,[2,6,2],5,1},{2,3,4,[2,6,2,5],{2,3,4,2,6,[2,5],{2,5,1},{2,3,4,2,5,{2,5,1}}の6つである
Java実装:

/**
 * 
 * @author ChopinXBP
 *               ，               。
 *   ，      {2,3,4,2,6,2,5,1}        3，      6     ，         {4,4,6,6,6,5}；
 *     {2,3,4,2,6,2,5,1}        6 ： 
 * {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， 
 * {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
 * 
 */

import java.util.ArrayList;
import java.util.LinkedList;

public class maxInWindows_63 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] num = {2,3,4,2,6,2,5,1};
		ArrayList result = maxInWindows(num, 3);
		for(int i = 0; i < result.size(); i++) {
			System.out.print(result.get(i) + " ");
		}
	}

    public static ArrayList maxInWindows(int [] num, int size)
    {
    	ArrayList result = new ArrayList<>();
    	if(num == null || size <= 0 || size > num.length) return result;
    	//          （     ）	
    	LinkedList list = new LinkedList<>();
    	//      ，            k        ：          k        ，    k    ，        
    	for(int i = 0; i < size - 1; i++) {
    		while(!list.isEmpty() && num[i] > num[list.peekFirst()]) {
    			list.pollFirst();
    		}
    		list.addFirst(i);
    	}
    	
    	//         size - 1 ，        k = num[i]    	
    	for(int i = size - 1; i < num.length; i++) {
    		//       k    ， k    
    		while(!list.isEmpty() && num[i] > num[list.peekFirst()]) {
    			list.pollFirst();
    		}
    		list.addFirst(i);
    		//      （        ）        （     ），      （          ）
    		if(i - list.peekLast() + 1 > size) {
    			list.pollLast();
    		}
    		result.add(num[list.peekLast()]);
    	}
    	  	
    	return result;
    }	
}

C++実装例:

class Solution {
public:
    vector maxInWindows(const vector& num, unsigned int size)
    {
        vector res;
        deque s;
        for(unsigned int i=0;isize)
                s.pop_front();

            //      num      
            s.push_back(i);

            //        i    size           
            if(size&&i+1>=size)
                res.push_back(num[s.front()]);
        }
        return res;
    }
};

#Coding 1時間、Copying 1秒.いいねを残してくれてありがとう