LeetCode-376

376. 摆动序列(Wiggle Subsequence)

原题链接


描述

如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为 摆动序列 。第一个差(如果存在的话)可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如, [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ,因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

相反,[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列,第一个序列是因为它的前两个差值都是正数,第二个序列是因为它的最后一个差值为零。
子序列 可以通过从原始序列中删除一些(也可以不删除)元素来获得,剩下的元素保持其原始顺序。

给你一个整数数组 nums ,返回 nums 中作为 摆动序列 的 最长子序列的长度 。


示例

Input: nums = [1,7,4,9,2,5]
Output: 6
Explanation: The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).

思路

贪心。首先,如果它不为空,那么序列长度至少会是一。序列中相邻元素的关系只有四种:相等、递增、递减、增减摆动(题目中要求的情况)。

  • 首先如果是相等,那么是不影响的因为当前元素和前一个元素相等,那么和后面元素的差也是相等的,直接跳过即可;
  • 递增或者递减。以递增为例,如果是递增,那么永远保存最大的那个数,因为如果小数字可以和后面的数字构成摆动序列的话,大数字一定可以,因为当前是递增的,摆动序列中该数的下一个数一定小于该数。即:a<b,那么 a 一定小于 x ( x > b )举例3,4,7,5,6
  • 增减摆动,就是判断上一次的运算结果和当前运算结果异或结果是否为 true,是的话摆动序列元素加一。

根据这些关系,当一个数和保存的前一个数(不一定是相邻的)之差 和上一次的差点结果不同时,即可判断当前元素属于百摆动序列。


解答

public class Solution {
    public int wiggleMaxLength(int[] nums) {

        if (nums.length <= 1) return nums.length;
        int cnt = 1;
        int tmp = nums[1];
        boolean flag = true;//第一次
        boolean zf = false;//上一次的正负 true ~ 正, false ~ 负
        for (int i = 1; i < nums.length; i++) {
            if (flag) {
                if (nums[i] - nums[i - 1] != 0) {
                    cnt++;
                    zf = nums[i] - nums[i - 1] > 0;
                    flag = false;
                    tmp = nums[i];
                }
            }
            else {
                if (nums[i] - tmp== 0)continue;
                boolean test = nums[i] - tmp > 0;
                //异号
                // 异或不是与
                if ((test ^ zf)){
                    cnt++;
                    zf = test;
                }
                tmp= nums[i];
            }

        }
        return cnt;
    }
}

LeetCode-376

上一篇:[b01lers2020]Welcome to Earth


下一篇:[CentOS7]firewalld 端口转发