Hard

题目描述

给定一个整数数组 nums。

如果一个子序列按顺序读取时不包含三个连续的相同奇偶性元素，则该子序列是稳定的（即在子序列内部连续）。

返回稳定子序列的数量。

由于答案可能很大，请返回模 10^9 + 7 的结果。

示例 1：

输入：nums = [1,3,5]
输出：6
解释：
稳定的子序列有 [1]、[3]、[5]、[1, 3]、[1, 5] 和 [3, 5]。
子序列 [1, 3, 5] 不稳定，因为它包含三个连续的奇数。因此答案是 6。

示例 2：

输入：nums = [2,3,4,2]
输出：14
解释：
唯一不稳定的子序列是 [2, 4, 2]，它包含三个连续的偶数。
所有其他子序列都是稳定的。因此答案是 14。

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

解题思路

这是一道动态规划题目。我们需要统计所有稳定子序列的数量。

核心思路：

  1. 状态定义：对于每个位置，我们维护四个状态：

    • dp0：空子序列数量（始终为1）
    • dp1_odd：以奇数结尾且长度为1的子序列数量
    • dp1_even：以偶数结尾且长度为1的子序列数量
    • dp2_odd：以奇数结尾且连续奇数长度为2的子序列数量
    • dp2_even：以偶数结尾且连续偶数长度为2的子序列数量

  2. 状态转移：对于当前数字 nums[i]：

    • 如果是奇数：
      • 可以单独形成新的长度为1的奇数子序列：new_dp1_odd = dp0 + dp1_even + dp2_even
      • 可以延续已有的奇数序列形成长度为2的连续奇数：new_dp2_odd = dp1_odd
      • 偶数相关状态保持不变
    • 如果是偶数：类似处理

  3. 关键点：

    • 长度为1或2的子序列总是稳定的
    • 只有当添加第三个相同奇偶性元素时才会违反稳定性
    • 每次遇到不同奇偶性的元素时，连续计数重置为1

  4. 最终答案：所有非空子序列的总和，即 dp1_odd + dp1_even + dp2_odd + dp2_even

代码实现

class Solution {
public:
    int countStableSubsequences(vector<int>& nums) {
        const int MOD = 1000000007;
        
        long long dp1_odd = 0, dp1_even = 0;
        long long dp2_odd = 0, dp2_even = 0;
        
        for (int num : nums) {
            if (num % 2 == 1) { // 奇数
                long long new_dp2_odd = dp1_odd;
                long long new_dp1_odd = (1 + dp1_even + dp2_even) % MOD;
                
                dp2_odd = new_dp2_odd;
                dp1_odd = new_dp1_odd;
            } else { // 偶数
                long long new_dp2_even = dp1_even;
                long long new_dp1_even = (1 + dp1_odd + dp2_odd) % MOD;
                
                dp2_even = new_dp2_even;
                dp1_even = new_dp1_even;
            }
        }
        
        return (dp1_odd + dp1_even + dp2_odd + dp2_even) % MOD;
    }
};

class Solution:
    def countStableSubsequences(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        
        dp1_odd = dp1_even = 0
        dp2_odd = dp2_even = 0
        
        for num in nums:
            if num % 2 == 1:  # 奇数
                new_dp2_odd = dp1_odd
                new_dp1_odd = (1 + dp1_even + dp2_even) % MOD
                
                dp2_odd = new_dp2_odd
                dp1_odd = new_dp1_odd
            else:  # 偶数
                new_dp2_even = dp1_even
                new_dp1_even = (1 + dp1_odd + dp2_odd) % MOD
                
                dp2_even = new_dp2_even
                dp1_even = new_dp1_even
        
        return (dp1_odd + dp1_even + dp2_odd + dp2_even) % MOD

public class Solution {
    public int CountStableSubsequences(int[] nums) {
        const int MOD = 1000000007;
        
        long dp1Odd = 0, dp1Even = 0;
        long dp2Odd = 0, dp2Even = 0;
        
        foreach (int num in nums) {
            if (num % 2 == 1) { // 奇数
                long newDp2Odd = dp1Odd;
                long newDp1Odd = (1 + dp1Even + dp2Even) % MOD;
                
                dp2Odd = newDp2Odd;
                dp1Odd = newDp1Odd;
            } else { // 偶数
                long newDp2Even = dp1Even;
                long newDp1Even = (1 + dp1Odd + dp2Odd) % MOD;
                
                dp2Even = newDp2Even;
                dp1Even = newDp1Even;
            }
        }
        
        return (int)((dp1Odd + dp1Even + dp2Odd + dp2Even) % MOD);
    }
}

var countStableSubsequences = function(nums) {
    const MOD = 1000000007;
    const n = nums.length;
    
    // dp[i][j][k] = number of stable subsequences ending at index i
    // j = parity of last element (0 for even, 1 for odd)
    // k = length of consecutive elements with same parity at the end (1 or 2)
    const dp = Array(n).fill().map(() => Array(2).fill().map(() => Array(3).fill(0)));
    
    // Base case: single element subsequences
    const parity = nums[0] % 2;
    dp[0][parity][1] = 1;
    
    let result = 1; // Count the first element
    
    for (let i = 1; i < n; i++) {
        const currParity = nums[i] % 2;
        const oppParity = 1 - currParity;
        
        // Single element subsequence
        dp[i][currParity][1] = (dp[i][currParity][1] + 1) % MOD;
        
        // Extend previous subsequences
        for (let j = 0; j < i; j++) {
            // Extend subsequences ending with opposite parity
            if (dp[j][oppParity][1] > 0) {
                dp[i][currParity][1] = (dp[i][currParity][1] + dp[j][oppParity][1]) % MOD;
            }
            if (dp[j][oppParity][2] > 0) {
                dp[i][currParity][1] = (dp[i][currParity][1] + dp[j][oppParity][2]) % MOD;
            }
            
            // Extend subsequences ending with same parity (length 1)
            if (dp[j][currParity][1] > 0) {
                dp[i][currParity][2] = (dp[i][currParity][2] + dp[j][currParity][1]) % MOD;
            }
        }
        
        result = (result + dp[i][currParity][1] + dp[i][currParity][2]) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)遍历数组一次，每次操作为常数时间
空间复杂度O(1)只使用固定数量的变量存储状态