376. 摆动序列

link

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

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

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

思路 1：贪心

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。

整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）。每一步都只关注当前是否能构成“拐点”（即构成一个有效的“摆动”），而不是枚举所有子序列进行动态规划选择。

在计算是否有峰值的时候，通过遍历下标 i ，计算 prediff(nums[i] - nums[i-1]) 和 curdiff(nums[i+1] - nums[i])，如果 prediff < 0 && curdiff > 0 或者 prediff > 0 && curdiff < 0 此时就有波动就需要统计。

需要注意以下两点：

初始化：
- 序列长度小于 2 时，无法计算元素差，所以直接返回序列长度
- count 的初始值问题，如果前两个元素的差为 0，则 count 为 1（当前摆动序列只算一个数字）；否则为 2（前两个数字全部算入摆动序列中）
条件判断：
- pre == 0 的情况，相当于前一对没有进行变化，如果此时的 cur != 0，则说明遇到了第一个波动，需要记录

详细的案例分析见代码随想录

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        if len(nums) < 2:
            return len(nums)
        
        pre = nums[1] - nums[0]
        if pre != 0:
            count = 2
        else:
            count = 1

        for i in range(1, len(nums) - 1):
            cur = nums[i + 1] - nums[i]
            if (cur > 0 and pre <= 0) or (cur < 0 and pre >= 0):
                count += 1
                pre = cur

        return count

738.单调递增的数字

link

当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。给定一个整数 n ，返回小于或等于 n 的最大数字，且数字呈单调递增。

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

思路

例如：98，一旦出现 strNum[i - 1] > strNum[i] 的情况（非单调递增），首先想让 strNum[i - 1]–，然后 strNum[i] 给为9，这样这个整数就是 89，即小于 98 的最大的单调递增整数。

这样就只能从后往前遍历了。因为需要先确定大的数字。整体流程为：反向遍历，如果当前数字小于前一个，则前一位“借 1”，当前位置之后的所有数字都设置为 9

class Solution:
    def monotoneIncreasingDigits(self, n: int) -> int:
        num = list(str(n))

        for i in range(len(num) - 1, 0, -1):
            if num[i] < num[i - 1]:
                num[i - 1] = str(int(num[i - 1]) - 1)

                for j in range(i, len(num)):
                    num[j] = '9'
        return int(''.join(num))