吴师兄学算法day08 贪心 376. 摆动序列

题目：376. 摆动序列

难点：

• 理解难。思路不好想
• 看了卡尔的思路。
• 可以先去重，再遍历。

我的代码加调试：

from typing import List


# 摆动序列
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:

        if len(nums) == 1:
            return 1
        # 1.先去重把
        new_nums = []
        for i in range(len(nums)):
            if i == 0 or nums[i] != nums[i - 1]:  # 只要不等于前1个，就添加进来 第一个无论怎样都要加进来
                new_nums.append(nums[i])
        # print(new_nums)
        if len(new_nums) == 1: return 1  # 例如 [2,2,2,2]

        if len(new_nums) == 2: return 2  # 例如 [3,2,2,2,2]
        # 2.现在至少有3个元素了
        # 判断前一个后一个的正负
        res = 2  # 默认包含最两边的
        for i in range(1, len(new_nums) - 1):  # 不算两边的 简化判断
            # 这里注意要每次用后面减去前面的
            # print(f"现在遍历的元素是{nums[i]},前结果{new_nums[i] - new_nums[i - 1]},后结果{new_nums[i+1] - new_nums[i]}")
            if (new_nums[i] - new_nums[i - 1]) * (new_nums[i+1] - new_nums[i]) < 0:  # 一正一负
                # print("===")
                res += 1
        return res


if __name__ == '__main__':
    obj = Solution()
    # obj.wiggleMaxLength([3, 2, 2, 2, 2, 2, 2, 2]) # 1.去重测试
    res = obj.wiggleMaxLength([3, 2, 3, 2, 2, 2, 2, 2]) # 2.测试
    print("结果:",res)

老师的思路：

记录上升状态和下降状态。

老师的代码：

# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 摆动序列(376):https://leetcode-cn.com/problems/wiggle-subsequence/
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        # 每个元素都有三种状态

        # 1、每个元素的初始状态
        beginState = 0

        # 2、如果当前元素的值大于它之前元素的值
        # 比如 nums[i] > nums[i-1]
        # 那么说明当前元素处于上升阶段，状态设置为 up
        upState = 1


        # 3、如果当前元素的值小于它之前元素的值
        # 比如 nums[i] < nums[i-1]
        # 那么说明当前元素处于下降阶段，状态设置为 down
        downState = 2

        # 如果 nums 长度小于 2 
        if len(nums) < 2 :
            # 由于仅有一个元素或者含两个不等元素的序列也视作摆动序列
            # 直接返回数组的长度
            return len(nums)
        

        # 以第一个元素作为初始的摇摆序列，此时，长度为 1
        length = 1

        # 一开始，状态为 begin
        state = beginState

        # 接下来，开始遍历 nums 中的所有元素
        for i in range(1 ,len(nums)) :
            # 每个元素都有三种状态，在这三种状态下去判断这个元素应该怎么操作

            # 1、如果是在 begin 状态
            if state == beginState :
                # 那么比较 nums[i] 和  nums[i-1] 的大小

                # 此时的元素值为 nums[i]，它前面的元素值为 nums[i-1]
                # 如果 nums[i] > nums[i-1]，代表着现在处于上升过程
                if nums[i] > nums[i-1] :
                    # 状态修改为 up
                    state = upState
                    # 摆动序列中增加了 nums[i] 这个元素，所以 length 需要加 1
                    length += 1

                # 此时的元素值为 nums[i]，它前面的元素值为 nums[i-1]
                # 如果 nums[i] < nums[i-1]，代表着现在处于下降过程
                elif nums[i] < nums[i-1] :
                    # 状态修改为 down
                    state = downState
                    # 摆动序列中增加了 nums[i] 这个元素，所以 length 需要加 1
                    length += 1

            # 2、如果是在 up 状态
            # 说明 nums[i] 的前面两个元素 nums[i-2] < nums[i-1]，正在处于上升过程
            elif state == upState :

                # 只有此时 nums[i] < nums[i-1]
                # 那么 nums[i-2]，nums[i-1]，nums[i] 这三者形成一个波峰  ^
                if nums[i] < nums[i-1] :
                    
                    # 此时，由于 nums[i] < nums[i-1]，开始处于下降状态了
                    # 状态修改为 down
                    state = downState
                    # 摆动序列中增加了 nums[i] 这个元素，所以 length 需要加 1
                    length += 1
            # 3、如果是在 up 状态
            # 说明 nums[i] 的前面两个元素 nums[i-2] > nums[i-1]，正在处于下降过程
            elif state == downState :

                # 只有此时 nums[i] > nums[i-1]
                # 那么 nums[i-2]，nums[i-1]，nums[i] 这三者形成一个波谷 V
                if nums[i] > nums[i-1] :

                    # 此时，由于 nums[i] > nums[i-1]，开始处于上升状态了
                    # 状态修改为 up                    
                    state = upState
                    # 摆动序列中增加了 nums[i] 这个元素，所以 length 需要加 1
                    length += 1

        # 返回结果 length
        # 不需要返回具体序列
        return length

卡尔的写法：

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if len(nums) <= 1:
            return len(nums)  # 如果数组长度为0或1，则返回数组长度
        preDiff,curDiff ,result  = 0,0,1  #题目里nums长度大于等于1，当长度为1时，其实到不了for循环里去，所以不用考虑nums长度
        for i in range(len(nums) - 1):
            curDiff = nums[i + 1] - nums[i]
            if curDiff * preDiff <= 0 and curDiff !=0:  #差值为0时，不算摆动
                result += 1
                preDiff = curDiff  #如果当前差值和上一个差值为一正一负时，才需要用当前差值替代上一个差值
        return result

总结：

• 感觉卡尔的代码更简洁。目前先过掉这题。
• 下次再来一遍的时候，可以在研究

参考：

卡尔 ：https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html