Txing

欢迎来到 | 伽蓝之堂

0%

Q376-摆动序列-中等-贪心

Posted on In
Symbols count in article: 4.1k Reading time ≈ 4 mins.
Q376-摆动序列-中等-贪心

376. 摆动序列

Question

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

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

  • 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

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

Example 1:

输入：nums = [1,7,4,9,2,5] 输出：6 解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

Example 2:

输入：nums = [1,17,5,10,13,15,10,5,16,8] 输出：7 解释：这个序列包含几个长度为 7 摆动序列。 其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

Note:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

Approach 1: 贪心

一开始没看到可以删减元素，打算使用双循环，遍历每个元素作为开头的子序列，计算最长的摇摆子序列。但是跑例子2的时候处了问题。

后来发现可以删除元素，所以考虑第二层循环里面不同加break了，可以继续计数，同时考虑了几个特殊情况，例如 输出 1, 输出 2 等。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        N = len(nums)
        if N == 1 or (N == 2 and nums[0] == nums[1]):
            return 1
        ans = 1

        for i in range(1,N-1):
            dif_old = nums[i] - nums[i-1]
            length = 2
            for j in range(i+1,N):
                dif_new = nums[j] - nums[j-1]
                if dif_old * dif_new < 0:
                    length += 1
                    ans = max(length,ans)
                    dif_old = dif_new
                elif dif_new != 0:
                    ans = max(length,ans)
                    dif_old = dif_new
        return ans

进一步补考虑，实际上由于删除机制，最长的子序列一定是从头开始计数的，所以可以去掉第一层循环，减小时间复杂度从O(n^2)到O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def wiggleMaxLength(self, nums) -> int:
        N = len(nums)
        if N == 1 or (N == 2 and nums[0] == nums[1]):
            return 1
        ans = 1

        dif_old = nums[1] - nums[0]
        length = 2
        for j in range(1,N):
            dif_new = nums[j] - nums[j-1]
            if dif_old * dif_new < 0:
                length += 1
                ans = max(length,ans)
                dif_old = dif_new
            elif dif_new != 0:
                ans = max(length,ans)
                dif_old = dif_new
        return ans

复杂度分析

  • 时间复杂度：，N是序列长度。
  • 空间复杂度：。常数个变量。

Approach 2: 动态规划

每当我们选择一个元素作为摆动序列的一部分时，这个元素要么是上升的，要么是下降的，这取决于前一个元素的大小。那么列出状态表达式为：

  • 表示以前 i 个元素中的某一个为结尾的最长的「上升摆动序列」的长度。

  • 表示以前 i 个元素中的某一个为结尾的最长的「下降摆动序列」的长度。

下面以 up[i] 为例，说明其状态转移规则：

  • 当 时，我们无法选出更长的「上升摆动序列」的方案。因为对于任何以 结尾的「上升摆动序列」，我们都可以将 替换为 ，使其成为以 结尾的「上升摆动序列」。
  • 当 时，我们既可以从 进行转移，也可以从 进行转移。下面我们证明从 转移是必然合法的，即必然存在一个 对应的最长的「下降摆动序列」的末尾元素小于 。
    • 我们记这个末尾元素在原序列中的下标为 j，假设从 j 往前的第一个「谷」为 nums[k]，我们总可以让 j 移动到 k，使得这个最长的「下降摆动序列」的末尾元素为「谷」。
    • 然后我们可以证明在这个末尾元素为「谷」的情况下，这个末尾元素必然是从 nums[i] 往前的第一个「谷」。证明非常简单，我们使用反证法，如果这个末尾元素不是从 nums[i] 往前的第一个「谷」，那么我们总可以在末尾元素和 nums[i] 之间取得一对「峰」与「谷」，接在这个「下降摆动序列」后，使其更长。
    • 这样我们知道必然存在一个 down[i−1] 对应的最长的「下降摆动序列」的末尾元素为 nums[i] 往前的第一个「谷」。这个「谷」必然小于 nums[i]。证毕。

这样我们可以用同样的方法说明 down[i] 的状态转移规则，最终的状态转移方程为：

最终的答案即为 up[n−1] 和 down[n−1] 中的较大值，其中 n 是序列的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return n

        up = [1] + [0] * (n - 1)
        down = [1] + [0] * (n - 1)
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                up[i] = max(up[i - 1], down[i - 1] + 1)
                down[i] = down[i - 1]
            elif nums[i] < nums[i - 1]:
                up[i] = up[i - 1]
                down[i] = max(up[i - 1] + 1, down[i - 1])
            else:
                up[i] = up[i - 1]
                down[i] = down[i - 1]

        return max(up[n - 1], down[n - 1])

复杂度分析

  • 时间复杂度：O(n)，其中 n 是序列的长度。我们只需要遍历该序列一次。

  • 空间复杂度：O(n)，其中 n 是序列的长度。我们需要开辟两个长度为 n 的数组。

Approach 3: 优化的动态规划

思路及解法

注意到方法一中，我们仅需要前一个状态来进行转移，所以我们维护两个变量即可。这样我们可以写出如下的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return n

        up = down = 1
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                up = max(up, down + 1)
            elif nums[i] < nums[i - 1]:
                down = max(up + 1, down)

        return max(up, down)

注意到每有一个「峰」到「谷」的下降趋势， 值才会增加，每有一个「谷」到「峰」的上升趋势， 值才会增加。且过程中 与 的差的绝对值值恒不大于 1，即 且 ，于是有 且 。这样我们可以省去不必要的比较大小的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 2:
            return n

        up = down = 1
        for i in range(1, n):
            if nums[i] > nums[i - 1]:
                up = down + 1
            elif nums[i] < nums[i - 1]:
                down = up + 1

        return max(up, down)

复杂度分析

时间复杂度：O(n)，其中 n 是序列的长度。我们只需要遍历该序列一次。

空间复杂度：O(1)。我们只需要常数空间来存放若干变量。