アルゴリズム-欲張り-スイングシーケンス(スイングシーケンス)

アルゴリズム-欲張り-スイングサブシーケンス(スイングサブシーケンス/Wiggle Subsequence)
1テーマの概要
1.1テーマの出典
https://leetcode-cn.com/problems/wiggle-subsequence/solution/bai-dong-xu-lie-by-leetcode/
1.2テーマ説明
連続する数値の差が正と負の間で厳密に交互になる場合、数値シーケンスをスイングシーケンスと呼ぶ.最初の差(存在する場合)は正数または負数である可能性があります.2つ未満の要素のシーケンスもスイングシーケンスです.
例えば、[1,7,4,9,2,5]は、差分値(6,−3,5,−7,3)が正負交互に現れるため、揺動シーケンスである.逆に,[1,4,7,2,5]および[1,7,4,5,5]は揺動シーケンスではなく,第1のシーケンスはその最初の2つの差が正数であるため,第2のシーケンスはその最後の差がゼロであるためである.
整数シーケンスが与えられ、ウォブルシーケンスとしての最上位シーケンスの長さが返される.元のシーケンスからいくつかの(削除しなくてもよい)要素を削除することによってサブシーケンスが得られ、残りの要素は元の順序を維持します.
例1:
入力:[1,7,4,9,2,5]出力:6解釈:シーケンス全体が揺動シーケンスである.例2:
入力:[1,17,5,10,13,15,10,5,16,8]出力:7説明:このシーケンスは長さ7の揺動シーケンスをいくつか含み、そのうちの1つは[1,17,10,13,10,16,8]であってもよい.例3:
入力:[1,2,3,4,5,6,7,8,9]出力:2進級:O(n)時間の複雑さでこの問題を完成できますか?
2問題解
2.1欲張り法
2.1.1問題解決の考え方

上向きの傾向であれば、上向きの傾向の最後の点が以前の合法的な点に取って代わるまで取る.

下向きのトレンドであれば、下向きのトレンドの最後のポイントが以前の合法的なポイントに代わるまで取得されます.

は、実際には不要な点を削除することに相当し、局所最大/最小点を保持して規則に合致する曲がり点図

を形成する.
2.1.2コード

class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(null == nums){
            return 0;
        }

        if(nums.length < 2){
            return nums.length;
        }

        int symbol = 0;

        //      1 ，           1
        int max = 1;
        for(int i = 1; i < nums.length; i++){
            if(nums[i] - nums[i-1] > 0 && symbol <= 0){
                // 1.      ，          ，     ，  ：
                //  1.1            
                //  1.2         
                max++;
                symbol = symbol == 0;
            }else if(nums[i] - nums[i-1] < 0 && symbol >= 0){
                // 2.       ，          ，     ，  ：
                //  2.1            
                //  2.2         
                max++;
                symbol = -1;
            }
            //                       ，     0
            //        ，           
            //        ，        ，                       ;
            //         ，                       。
            //                ，       /             
        }
        return max;
    }
}

2.1.2時間複雑度
O(n)
2.1.3空間複雑度
O(1)
2.2動的計画
2.2.1問題解決の考え方
2.2.2コード
2.2.2時間複雑度
2.2.3空間複雑度
リファレンスドキュメント

揺動シーケンス-公式解法