2026-02-26：锯齿形数组的总数Ⅰ。用go语言，给定三个整数 n、l、r，要求构造长度为 n 的数组，元素取自区间 [l, r]，并满足以下两条规则：

• 相邻两个位置上的数不能相等；

• 任意连续的三个数既不能形成严格单调上升的三元组，也不能形成严格单调下降的三元组。

求满足上述条件的数组数量，并将结果对 1000000007 取模后返回。

说明：

• “严格单调上升”意指每一项都比前一项大；

• “严格单调下降”意指每一项都比前一项小。

3 <= n <= 2000。

1 <= l < r <= 2000。

输入：n = 3, l = 4, r = 5。

输出：2。

解释：

在取值范围 [4, 5] 内，长度为 n = 3 的锯齿形数组只有 2 种：

[4, 5, 4]
[5, 4, 5]

题目来自力扣3699。

一、核心规则与问题转化（理解代码的前提）

首先明确题目规则的本质：

1. 相邻数不能相等；
2. 连续三个数不能严格递增（如a<b<c）或严格递减（如a>b>c）；
   → 推导可得：满足条件的数组必须是严格的“锯齿形”（即上升、下降、上升… 或 下降、上升、下降…），且长度为n的数组只有两种基础模式：
   • 模式1：位置1 < 位置2 > 位置3 < 位置4 …
   • 模式2：位置1 > 位置2 < 位置3 > 位置4 …
     代码中最终结果乘以2，正是对应这两种模式的总数之和。

以输入 n=3, l=4, r=5 为例，取值范围只有4、5两个数，符合条件的只有 [4,5,4]（模式1）和 [5,4,5]（模式2），总数为2，与输出一致。

二、代码执行过程分步解析（以n=3, l=4, r=5为例）

步骤1：初始化核心变量

• mod = 1e9+7：用于结果取模，避免数值溢出；
• k = r - l + 1：计算取值范围的元素个数，本例中 k=5-4+1=2；
• f := make([]int, k)：创建长度为k的动态规划（DP）数组，f[j] 表示“以第j个数值（对应区间[l, r]中的l+j）结尾的、满足条件的数组数量”；
• 初始化 f 所有元素为1：因为数组长度为1时（i=0），每个数值都可以作为起始元素，数量为1。本例中 f = [1, 1]（对应数值4、5）。

步骤2：动态规划迭代（i从1到n-1，对应数组长度从2到n）

循环变量 i 表示“当前构造到数组的第i个位置”（数组索引从0开始），i%2 控制当前位置的增减规则：

• i%2 > 0（i为奇数，对应数组第2个位置）：要求当前位置比前一个位置大（对应模式1的上升段）；
• i%2 == 0（i为偶数，对应数组第3个位置）：要求当前位置比前一个位置小（对应模式1的下降段）。

子步骤2.1：i=1（构造数组第2个位置，要求“增”）

i=1 是奇数，执行“增”的逻辑：

• 目标：计算以每个数值结尾、且比前一个数值大的数组数量；
• 核心逻辑：pre 记录“比当前数值小的所有数值的数量之和”（因为要满足前小后大）；
• 遍历 f 数组（j=0到1）：
  • j=0（对应数值4）：没有比4更小的数 → f[0] = pre = 0，pre += 原f[0] = 1（pre变为1）；
  • j=1（对应数值5）：比5小的数是4（j=0），数量和为1 → f[1] = pre = 1，pre += 原f[1] = 1（pre变为2）；
• 执行后 f = [0, 1]：表示数组长度为2时，以4结尾的有效数组数为0（没有数比4小且不相等），以5结尾的有效数组数为1（只有[4,5]）。

子步骤2.2：i=2（构造数组第3个位置，要求“减”）

i=2 是偶数，执行“减”的逻辑：

• 目标：计算以每个数值结尾、且比前一个数值小的数组数量；
• 核心逻辑：suf 记录“比当前数值大的所有数值的数量之和”（因为要满足前大后小）；
• 从后往前遍历 f 数组（j=1到0）：
  • j=1（对应数值5）：没有比5更大的数 → f[1] = suf = 0，suf += 原f[1] = 1（suf变为1）；
  • j=0（对应数值4）：比4大的数是5（j=1），数量和为1 → f[0] = suf = 1，suf += 原f[0] = 0（suf仍为1）；
• 执行后 f = [1, 0]：表示数组长度为3时，以4结尾的有效数组数为1（即[4,5,4]），以5结尾的有效数组数为0。

步骤3：计算单模式总数并扩展到两种模式

• 累加 f 数组所有元素：ans = 1 + 0 = 1（这是模式1的总数）；
• 乘以2：对应模式1和模式2的总数（模式2的计算逻辑与模式1对称，总数也是1），结果为 1×2=2；
• 对mod取模：最终结果为2，与题目输出一致。

三、时间复杂度与空间复杂度分析

1. 时间复杂度

• 初始化DP数组：O(k)，k为取值范围长度（r-l+1）；
• 动态规划主循环：
  • 外层循环：i从1到n-1，共n-1次，时间复杂度O(n)；
  • 内层循环（增/减逻辑）：每次遍历k个元素，时间复杂度O(k)；
    → 主循环总时间：O(n×k)；
• 结果累加：O(k)；
• 总时间复杂度：O(k) + O(n×k) + O(k) = O(n×k)；
  结合题目约束（n≤2000，k≤2000），最大计算量为2000×2000=4×10^6，完全符合性能要求。

2. 额外空间复杂度

• DP数组 f：长度为k，空间复杂度O(k)；
• 其他变量（pre、suf、ans等）：都是单个整型变量，空间复杂度O(1)；
• 总额外空间复杂度：O(k)；
  题目中k≤2000，空间开销极小。

总结

1. 核心过程：将问题转化为两种锯齿模式的计数之和，通过动态规划数组f记录“以每个数值结尾的有效数组数”，按奇偶位置交替执行“增/减”逻辑更新DP数组，最后累加单模式总数并乘以2得到最终结果；
2. 时间复杂度：O(n×k)（n为数组长度，k为取值范围长度）；
3. 额外空间复杂度：O(k)（仅需存储长度为k的DP数组）。

Go完整代码如下：

package main

import (
	"fmt"
)

func zigZagArrays(n, l, r int) (ans int) {
	const mod = 1_000_000_007
	k := r - l + 1
	f := make([]int, k)
	for i := range f {
		f[i] = 1
	}

	for i := 1; i < n; i++ {
		if i%2 > 0 { // 增
			pre := 0
			for j, v := range f {
				f[j] = pre % mod
				pre += v
			}
		} else { // 减
			suf := 0
			for j := k - 1; j >= 0; j-- {
				v := f[j]
				f[j] = suf % mod
				suf += v
			}
		}
	}

	for _, v := range f {
		ans += v
	}
	return ans * 2 % mod
}

func main() {
	n := 3
	l := 4
	r := 5
	result := zigZagArrays(n, l, r)
	fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

def zigZagArrays(n, l, r):
    mod = 1_000_000_007
    k = r - l + 1
    
    # f[j] 表示以值 l+j 结尾的当前长度的序列个数
    f = [1] * k
    
    for i in range(1, n):
        if i % 2 == 1:  # 奇数索引，需要上升
            pre = 0
            for j in range(k):
                # 对于位置 j，前面所有更小的数都可以接在它前面
                # 因为当前长度需要上升，所以结尾数字 j 前面必须小于 j
                pre_val = pre
                pre = (pre + f[j]) % mod
                f[j] = pre_val
        else:  # 偶数索引，需要下降
            suf = 0
            for j in range(k-1, -1, -1):
                # 对于位置 j，后面所有更大的数都可以接在它前面
                # 因为当前长度需要下降，所以结尾数字 j 前面必须大于 j
                suf_val = suf
                suf = (suf + f[j]) % mod
                f[j] = suf_val
    
    # 求和所有可能的结尾值
    ans = sum(f) % mod
    
    # 乘以2的原因：题目可能要求两种方向（先增后减或先减后增）
    # 但这里已经处理了奇偶的情况，可能需要根据实际题目调整
    return (ans * 2) % mod

def main():
    n = 3
    l = 4
    r = 5
    result = zigZagArrays(n, l, r)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1000000007;

long long zigZagArrays(int n, int l, int r) {
    int k = r - l + 1;

    // f[j] 表示以值 l+j 结尾的当前长度的序列个数
    vector<long long> f(k, 1);

    for (int i = 1; i < n; i++) {
        if (i % 2 == 1) {  // 奇数索引，需要上升
            long long pre = 0;
            for (int j = 0; j < k; j++) {
                long long v = f[j];
                f[j] = pre % MOD;
                pre = (pre + v) % MOD;
            }
        } else {  // 偶数索引，需要下降
            long long suf = 0;
            for (int j = k - 1; j >= 0; j--) {
                long long v = f[j];
                f[j] = suf % MOD;
                suf = (suf + v) % MOD;
            }
        }
    }

    // 求和所有可能的结尾值
    long long ans = 0;
    for (int j = 0; j < k; j++) {
        ans = (ans + f[j]) % MOD;
    }

    // 乘以2的原因：题目可能要求两种方向（先增后减或先减后增）
    // 但这里已经处理了奇偶的情况，可能需要根据实际题目调整
    return (ans * 2) % MOD;
}

int main() {
    int n = 3;
    int l = 4;
    int r = 5;
    long long result = zigZagArrays(n, l, r);
    cout << result << endl;
    return 0;
}