LeetCode 解題筆記：3699. Number of ZigZag Arrays I

作者：王一哲
日期：2026年6月23日


LeetCode 題目連結：3699. Number of ZigZag Arrays I

解題想法

困難題。題目要求的 ZigZag array 規則有兩個：

1. No two adjacent elements are equal. 相鄰的兩個數字不相等。
2. No three consecutive elements form a strictly increasing or strictly decreasing sequence. 沒有連續 3 個數字嚴格遞增或遞減。

如果要同時符合以上兩個條件，代表數字大小要交錯。這題要用動態規畫及前綴和解題，否則會超時。如果數字的範圍為 $[l, r]$，則可用的數字數量為 $k = r - l + 1$，開兩個陣列長度為 $k+1$ 的陣列 $up$ 及 $down$，$up[v]$ 代表最後一個數字為 $v$ 且 $v$ 大於前一個數字 $u$ 的方法數， $down[v]$ 代表最後一個數字為 $v$ 且 $v$ 小於前一個數字 $u$ 的方法數。初始化時先計算長度 $2$ 的方法數，$up[v] = v - 1$，因為 有 $v-1$ 個數字小於 $v$，$down[v] = k - v$，因為有 $k-v$ 個數字大於 $v$。由於更新長度 $3$ 到 $n$ 的過程中只需要用到前一個長度的方法數，可以用滾動陣列節省記憶體使用量。計算方法數要同時對 $MOD = 1000000007$ 取餘數，數值才不會過大。 用 Python 解題時遇到一個困難，如果計算前一個長度的方法數前綴和，需要用 itertools.accumulate 加速，如果用 list 會超時。

Python 程式碼

Runtime: 11142 ms, beats 26.32%. Memory: 20.20 MB, beats 28.95%.

from itertools import accumulate

class Solution:
    def zigZagArrays(self, n: int, l: int, r: int) -> int:
        MOD = 10**9 + 7  # 取餘數用的超大質數
        k = r - l + 1  # 可選的數字數量
        
        # 特例，k == 1，無法排出之字形的陣列，回傳 0
        if k == 1: return 0

        # 動態規畫
        up = [0] * (k+1)  # 最後一個數字 v 大於前一個數字 u 的方法數
        down = [0] * (k+1)  # 最後一個數字 v 小於前一個數字 u 的方法數
        # 初始化，長度為 2，假設選用數字 (u, v)
        for v in range(1, k+1):
            up[v] = v - 1  # 有 v-1 個數字小於 v
            down[v] = k - v  # 有 k-v 個數字大於 v
        # 更新長度 3 ~ n
        for _ in range(3, n+1):
            # 計算前綴和，要用 itertools.accumulate 才不會超時
            psum_up = list(accumulate(up))
            psum_down = list(accumulate(down))
            #psum_up = up[:]  
            #psum_down = down[:]
            #for v in range(1, k+1):
            #    psum_up[v] = (psum_up[v] + psum_up[v-1]) % MOD
            #    psum_down[v] = (psum_down[v] + psum_down[v-1]) % MOD
            # 新的方法數，更新 new_up[v] = psum_down[v-1] % MOD
            # new_down[v] = (psum_up[-1] - psum_up[v]) % MOD
            new_up = [0] + [psum_down[v-1] % MOD for v in range(1, k+1)]
            new_down = [0] + [(psum_up[-1] - psum_up[v]) % MOD for v in range(1, k+1)]
            # 交換新舊狀態
            up, new_up = new_up, up
            down, new_down = new_down, down
        # 更新完畢，答案為 up, down 所有長度方法數加總
        ans = 0
        for u, d in zip(up, down):
            ans = (ans + u + d) % MOD
        return ans

C++ 程式碼

Runtime: 1094 ms, beats 33.33%. Memory: 755.63 MB, beats 5.56%.

class Solution {
public:
    int zigZagArrays(int n, int l, int r) {
        const int MOD = 1000000007, k = r - l + 1;  // 取餘數用的超大質數，可選的數字數量
        
        // 特例，k == 1，無法排出之字形的陣列，回傳 0
        if (k == 1) return 0;

        // 動態規畫
        // up: 最後一個數字 v 大於前一個數字 u 的方法數
        // down: 最後一個數字 v 小於前一個數字 u 的方法數
        vector<int> up (k+1, 0), down (k+1, 0);
        // 初始化，長度為 2，假設選用數字 (u, v)
        for(int v = 1; v <= k; v++) {
            up[v] = v - 1;  // 有 v-1 個數字小於 v
            down[v] = k - v;  // 有 k-v 個數字大於 v
        }
        // 更新長度 3 ~ n
        for(int i = 3; i <= n; i++) {
            // 計算前綴和
            vector<int> psum_up (up.begin(), up.end()), psum_down (down.begin(), down.end());
            for(int v = 1; v <= k; v++) {
                psum_up[v] = (psum_up[v] + psum_up[v-1]) % MOD;
                psum_down[v] = (psum_down[v] + psum_down[v-1]) % MOD;
            }
            // 新的方法數，更新 new_up[v] = psum_down[v-1] % MOD
            // new_down[v] = (psum_up[-1] - psum_up[v]) % MOD
            vector<int> new_up (k+1, 0), new_down (k+1, 0);
            for(int v = 1; v <= k; v++) {
                new_up[v] = psum_down[v-1];
                new_down[v] = (psum_up.back() - psum_up[v] + MOD) % MOD;
            }
            // 交換新舊狀態
            swap(up, new_up);
            swap(down, new_down);
        }
        // 更新完畢，答案為 up, down 所有長度方法數加總
        int ans = 0;
        for(int v = 1; v <= k; v++) {
            ans = ((ans + up[v]) % MOD + down[v]) % MOD;
        }
        return ans;
    }
};