3753. Total Waviness of Numbers in Range II

題目 / Problem

中文： 給定兩個整數 num1 與 num2，代表一個閉區間 [num1, num2]。一個數字的「波動度（waviness）」定義為它所有「山峰」與「山谷」的數量：

某一位數字若嚴格大於左右兩個相鄰數字，它就是一個山峰（peak）。
某一位數字若嚴格小於左右兩個相鄰數字，它就是一個山谷（valley）。
一個數字的最高位與最低位永遠不能是山峰或山谷（因為它們各只有一個鄰居）。
位數少於 3 的數字，波動度一律為 0。

請回傳區間 [num1, num2] 內所有數字的波動度總和。

English: You are given two integers num1 and num2 describing an inclusive range [num1, num2]. The waviness of a number is the total count of its peaks and valleys:

A digit is a peak if it is strictly greater than both immediate neighbors.
A digit is a valley if it is strictly less than both immediate neighbors.
The first and last digits can never be peaks or valleys.
Any number with fewer than 3 digits has waviness 0.

Return the sum of waviness over every number in [num1, num2].

Constraints / 限制： 1 <= num1 <= num2 <= 10^15

Worked example / 範例： num1 = 120, num2 = 130 → output 3. 120 的中間位 2 是山峰（2 > 1 且 2 > 0）→ 波動度 1；121 的中間位 2 是山峰 → 1；130 的中間位 3 是山峰 → 1；其餘皆 0。總和 = 1 + 1 + 1 = 3。

名詞解釋 / Glossary

數位 DP / Digit DP（digit dynamic programming）：一種逐位（從最高位到最低位）建立數字、並用記憶化避免重複計算的技巧，常用來統計「0 到 N 之間滿足某條件的數字數量或某種總和」。Digit DP builds numbers one digit at a time and memoizes states, used to count or sum something over all numbers in [0, N].
前綴和式拆分 / Prefix decomposition f(N)：定義 f(N) = 區間 [0, N] 的波動度總和，則答案 = f(num2) − f(num1 − 1)。把「區間」問題轉成兩個「從 0 開始」的子問題。We define f(N) as the total waviness over [0, N]; the answer is f(num2) − f(num1−1).
tight 旗標 / tight flag：在逐位建立數字時，記錄「目前前綴是否仍緊貼上界 N 的前綴」。若 tight 為真，這一位最多只能放到 N 對應位的數字；若為假，這一位可自由放 0..9。Tracks whether the prefix we've built so far still equals N's prefix, which bounds the current digit.
前導零 / Leading zeros：為了讓所有數字「對齊」成相同位數，我們允許在前面補零（例如把 5 想成 005）。但這些補上的零不是「真正的數位」，不能參與山峰/山谷的判斷。We pad shorter numbers with leading zeros so all numbers share a length, but those zeros are not real digits.
哨兵值 / Sentinel value (10)：我們用 10 這個不可能的數位值代表「這個位置還沒有真正的數位」（仍處於前導零階段）。Using the impossible digit 10 to mark "no real digit yet."
記憶化 / Memoization：把已經算過的 DP 狀態結果存起來，下次遇到相同狀態直接取用，避免指數級重算。Caching computed DP states so each is solved once.
(數量, 總和) 配對 / (count, sum) pair：本題不是「數有幾個數字」，而是「加總波動度」。所以每個 DP 狀態同時回傳兩個值：該狀態下可形成的數字「個數」，以及這些數字累積的波動度「總和」。Each DP state returns both how many numbers it represents and the total waviness they accumulate.

思路

最直接的暴力做法是：從 num1 一路跑到 num2，對每個數字把它的數字一位一位拿出來，逐一檢查每個中間位是不是山峰或山谷，把波動度加起來。這在邏輯上完全正確，但 num2 最大到 10^15，逐一枚舉一千兆個數字絕對會超時，所以必須換思路。關鍵觀察是：我們不需要真的「列出」每個數字，而是要「統計」一個量（波動度總和）。這正是數位 DP 的用武之地。先把區間問題拆成 f(num2) − f(num1−1)，其中 f(N) 是 [0, N] 內所有數字的波動度總和；這樣只要會算「從 0 到某上界」的版本即可。接著我們從最高位往最低位逐位填數字，DP 的狀態需要記住：目前填到第幾位（pos）、是否仍緊貼上界（tight）、以及「最近放的兩個真實數位」——也就是 last（上一位）與 secondLast（上上位）。為什麼要記兩位？因為要判斷某一位 last 是不是山峰或山谷，必須同時知道它左邊的 secondLast 和右邊剛要放下去的 d。每當我們放下一個新數字 d 時，就能「回頭」判斷剛才那位 last：若 secondLast < last > d 它是山峰，若 secondLast > last < d 它是山谷，兩者都讓波動度 +1。為了正確處理長度不一的數字，我們用前導零把所有數字補齊，並用哨兵值 10 標記「還沒出現真正的數位」，這樣前導零就不會被誤判為鄰居。最後，因為要的是「總和」而不是「個數」，每個狀態回傳一個 (count, sum) 配對：放下 d 後若形成一個峰/谷（記為 e=1），則這條分支底下的每一個數字都要多加 e，所以新的總和是 子總和 + e × 子個數。記憶化所有非 tight 的狀態，整體就降到多項式時間。

The brute force is to iterate every number from num1 to num2, split each into digits, and check every interior digit for being a peak or valley. It is correct but hopeless: num2 can be 10^15, far too many numbers to enumerate. The trick is that we only need to count an aggregate (a sum of waviness), not list the numbers — exactly what digit DP is for. First decompose the range as f(num2) − f(num1−1), where f(N) is the total waviness over [0, N]; now we only need a "from zero up to a bound" routine. We build numbers digit by digit from the most significant position, and the DP state remembers: the current position (pos), whether the prefix is still pinned to the upper bound (tight), and the last two real digits placed — last (previous) and secondLast (the one before it). We keep two because deciding whether last is a peak/valley needs both its left neighbor secondLast and the digit d we are about to place to its right. Each time we place d, we look back at last: it is a peak when secondLast < last > d, a valley when secondLast > last < d; either adds 1 to waviness. To handle numbers of different lengths we pad with leading zeros and use a sentinel 10 to mark "no real digit yet," so leading zeros never masquerade as neighbors. Because we want a sum, every state returns a (count, sum) pair: if placing d creates a peak/valley (e = 1), each of the count numbers below gets +e, so the new sum is childSum + e × childCount. Memoizing all non-tight states brings the whole thing down to polynomial time.

逐步走查 / Walkthrough

我們挑統計流程中最核心的部分：如何在逐位放數字時偵測峰/谷。以區間第一個範例中的數字 120 為例（在 f(130) 的計算裡，這是其中一條被走到的路徑），看狀態如何變化。初始 last = 10（哨兵，表示尚無真實數位）、secondLast = 10、tight = true。

步驟 / Step	放下的位 `d` / place	放之前 `secondLast`, `last`	是否判定峰谷？ / peak-valley check	`e`	放之後 `secondLast`, `last`	說明 / Note
1	`1`	`10, 10`	`last==10`（尚無真位）→ 不判斷 / not started	0	`10, 1`	第一個真實數位，成為最高位 / first real digit
2	`2`	`10, 1`	`secondLast==10`（只有一位）→ 不判斷 / fewer than 2 real digits	0	`1, 2`	最高位無法是峰谷 / MSD can't be peak/valley
3	`0`	`1, 2`	`secondLast=1 < last=2 > d=0` → 山峰 peak!	1	`2, 0`	中間位 `2` 被判定為山峰 / middle digit is a peak

走查結束時，這條路徑（數字 120）累積的波動度為 e 總和 = 0 + 0 + 1 = 1，與題目敘述一致。0（最低位）永遠不會被判斷，因為它後面沒有再放任何數字——這正確地對應「最後一位不能是峰谷」。DP 會對 [0,130] 內所有路徑做同樣的事，並用 (count, sum) 把每條路徑的貢獻彙總起來，最後 f(130) − f(119) = 3。

We trace the heart of the algorithm — peak/valley detection while placing digits — on 120 (one path visited inside computing f(130)). Start with last = 10, secondLast = 10, tight = true. As the table shows, the digit 2 is detected as a peak exactly when we place the 0 after it (1 < 2 > 0), giving this path a waviness of 1. The leading sentinel and the "only one real digit" guard correctly skip the first digit, and the final 0 is never judged because nothing is placed after it — matching "the last digit can't be a peak or valley." The DP repeats this over every path and aggregates with (count, sum), ending at f(130) − f(119) = 3.

Solution — C

// 演算法 / Algorithm:
// 1) 區間拆分 / Range split: answer = f(num2) - f(num1-1), where f(N) = total
//    waviness over [0, N].
// 2) 數位 DP / Digit DP: build numbers MSB->LSB, state (pos, last, secondLast,
//    tight). When we place digit d, we judge whether `last` became a peak/valley
//    using (secondLast, last, d). Each state returns (count, sum) so we can sum
//    waviness, not just count numbers.

#include <string.h>   // 為了 memset 清空記憶化陣列 / for memset to clear memo

typedef long long ll; // 取別名，數值最大約 1.4e16 需要 64 位元 / 64-bit alias

// 記憶化陣列：索引為 [pos][last][secondLast]；last/secondLast 取 0..10（10 是哨兵）
// memo arrays indexed by [pos][last][secondLast]; values 0..10 (10 = sentinel)
static ll  cntMemo[16][11][11];  // 該狀態能形成的數字個數 / count of numbers
static ll  sumMemo[16][11][11];  // 該狀態累積的波動度總和 / accumulated waviness
static char vis[16][11][11];     // 該狀態是否已算過 / has this state been computed
static int dig[16];              // 上界 N 的每一位（最高位在 dig[0]）/ digits of N, MSB first
static int ndig;                 // N 的位數 / number of digits in N

// dp 透過指標回傳兩個值 cnt 與 sum / dp returns two values via pointers
// pos: 目前要填的位置 / current position to fill
// last: 上一個真實數位（10 表示還沒有真位）/ previous real digit (10 = none yet)
// sec : 上上個真實數位（10 表示不足兩位）/ digit before last (10 = fewer than two)
// tight: 前綴是否仍緊貼 N / is the prefix still equal to N's prefix
static void dp(int pos, int last, int sec, int tight, ll *cnt, ll *sum) {
    if (pos == ndig) {        // 已填完所有位，形成一個完整數字 / a full number formed
        *cnt = 1;             // 這是一個數字 / it is exactly one number
        *sum = 0;             // 它在此處不再新增波動度 / no further waviness here
        return;
    }
    // 非 tight 且算過 → 直接取快取 / if free (not tight) and cached, reuse it
    if (!tight && vis[pos][last][sec]) {
        *cnt = cntMemo[pos][last][sec];
        *sum = sumMemo[pos][last][sec];
        return;
    }

    int hi = tight ? dig[pos] : 9;  // tight 時這位最多放到 dig[pos]，否則放到 9
                                    // upper bound for this digit
    ll tc = 0, ts = 0;              // 本狀態累計的 count 與 sum / running totals

    for (int d = 0; d <= hi; d++) { // 嘗試這位放 0..hi 的每個數字 / try each digit d
        int nlast, nsec;            // 放完之後的新 last/secondLast / next state's digits
        ll e = 0;                   // 這步是否新增一個峰/谷（0 或 1）/ peak/valley gained

        if (last == 10) {           // 還在前導零階段 / still in the leading-zero phase
            if (d == 0) {           // 又放一個前導零 / another leading zero
                nlast = 10; nsec = 10;   // 仍視為「尚無真位」/ still "no real digit"
            } else {                // 第一個非零數位出現 / first nonzero digit appears
                nlast = d; nsec = 10;    // 它是最高位，前面沒有鄰居 / it's the MSD
            }
        } else {                    // 已有真實數位 / at least one real digit exists
            nsec = last;            // 舊的 last 變成新的 secondLast / shift left
            nlast = d;              // 新放下的 d 變成新的 last / d becomes last
            if (sec != 10) {        // 必須左右都有真鄰居才可能是峰/谷 / need both neighbors
                // last 的左鄰是 sec、右鄰是 d / last's neighbors are sec and d
                if ((last > sec && last > d) ||   // 比兩邊都大 → 山峰 / strictly greater = peak
                    (last < sec && last < d)) {   // 比兩邊都小 → 山谷 / strictly smaller = valley
                    e = 1;          // 這個數字此位多 1 波動度 / +1 waviness for this number
                }
            }
        }

        ll c, s;                    // 遞迴取得子問題的 (count, sum) / child results
        // tight 只有在這位剛好放到上界 d==hi 時才會延續 / stay tight only when d==hi
        dp(pos + 1, nlast, nsec, tight && (d == hi), &c, &s);

        tc += c;                    // 累加數字個數 / accumulate count
        ts += s + e * c;            // 子總和 + 本步每個數字各加 e / childSum + e per number
    }

    if (!tight) {                   // 只有非 tight 狀態能安全快取 / only free states are reusable
        vis[pos][last][sec] = 1;
        cntMemo[pos][last][sec] = tc;
        sumMemo[pos][last][sec] = ts;
    }
    *cnt = tc;                      // 透過指標把結果回傳 / hand results back via pointers
    *sum = ts;
}

// 計算 [0, N] 的波動度總和 / total waviness over [0, N]
static ll f(ll N) {
    if (N < 0) return 0;            // num1 可能為 1，N=num1-1 可能為 0；負數視為空 / guard

    int tmp[20], tn = 0;            // 暫存 N 的各位（最低位先取出）/ digits, LSB first
    if (N == 0) {                   // N==0 要特別處理，否則下方迴圈跑不到 / handle zero
        tmp[tn++] = 0;
    }
    ll t = N;
    while (t > 0) {                 // 反覆取餘數拆出每一位 / peel off digits by %10 and /10
        tmp[tn++] = (int)(t % 10);
        t /= 10;
    }
    ndig = tn;
    for (int i = 0; i < tn; i++)    // 反轉成最高位在前 / reverse so MSD is dig[0]
        dig[i] = tmp[tn - 1 - i];

    memset(vis, 0, sizeof(vis));    // 每次 f 都重置快取（位數可能不同）/ reset cache each call

    ll c, s;
    dp(0, 10, 10, 1, &c, &s);       // 從最高位開始，last/sec 皆為哨兵、tight=1 / start state
    return s;                       // 我們要的是波動度總和 / we want the sum
}

// LeetCode 入口函式 / entry point
long long totalWaviness(long long num1, long long num2) {
    return f(num2) - f(num1 - 1);   // 區間 = 上界前綴和 - 下界前綴和 / prefix-sum subtraction
}

Solution — C++

// 演算法 / Algorithm: identical to the C version.
// 1) answer = f(num2) - f(num1-1), f(N) = total waviness over [0, N].
// 2) Digit DP with state (pos, last, secondLast, tight), each state returning a
//    (count, sum) pair so we sum waviness rather than merely counting numbers.
// 3) Sentinel digit 10 marks "no real digit yet" to ignore leading zeros.

#include <vector>
#include <array>
#include <cstring>
using namespace std;

class Solution {
    using ll = long long;                 // 64 位元別名 / 64-bit alias

    vector<int> dig;                       // 上界 N 的各位，最高位在前 / digits of N, MSB first
    // memo[pos][last][sec] 存 (count, sum)；用 -1 標記未計算 / memo of (count,sum)
    // pair 是把兩個值打包在一起的標準容器 / std::pair bundles two values
    ll cntMemo[16][11][11];
    ll sumMemo[16][11][11];
    bool vis[16][11][11];

    // 回傳 (count, sum) / returns {count, sum} as a pair
    pair<ll, ll> dp(int pos, int last, int sec, bool tight) {
        if (pos == (int)dig.size())        // 填完所有位 → 一個完整數字 / full number
            return {1, 0};                 // 一個數字、此處無新增波動度 / one number, +0

        // 非 tight 且已快取就直接回傳 / reuse cached free states
        if (!tight && vis[pos][last][sec])
            return {cntMemo[pos][last][sec], sumMemo[pos][last][sec]};

        int hi = tight ? dig[pos] : 9;     // 這位的上界 / upper bound for this digit
        ll tc = 0, ts = 0;                 // 累計 count 與 sum / running totals

        for (int d = 0; d <= hi; ++d) {    // range-for 不適用，這裡用一般 for 列舉數字
            int nlast, nsec;               // 下一狀態的 last/secondLast / next digits
            ll e = 0;                      // 本步是否形成峰/谷 / peak-or-valley gained

            if (last == 10) {              // 仍在前導零階段 / leading-zero phase
                if (d == 0) { nlast = 10; nsec = 10; }   // 再一個前導零 / another zero
                else        { nlast = d;  nsec = 10; }   // 第一個真實數位 / first real digit
            } else {                       // 已有真實數位 / have real digits already
                nsec = last;               // 左移：last → secondLast / shift
                nlast = d;                 // d 成為新的 last / d becomes last
                if (sec != 10) {           // 兩側都有真鄰居才判斷 / need both neighbors
                    if ((last > sec && last > d) ||      // 山峰 / peak
                        (last < sec && last < d))        // 山谷 / valley
                        e = 1;             // 為此數字 +1 波動度 / +1 waviness
                }
            }

            // 結構化綁定：把 pair 拆成兩個變數 / structured bindings unpack the pair
            auto [c, s] = dp(pos + 1, nlast, nsec, tight && (d == hi));
            tc += c;                       // 累加數字個數 / accumulate count
            ts += s + e * c;               // 子總和 + 本步每數字各加 e / add this step's gain
        }

        if (!tight) {                      // 只快取非 tight 狀態 / cache only free states
            vis[pos][last][sec] = true;
            cntMemo[pos][last][sec] = tc;
            sumMemo[pos][last][sec] = ts;
        }
        return {tc, ts};
    }

    ll f(ll N) {                           // [0, N] 的波動度總和 / total waviness over [0, N]
        if (N < 0) return 0;               // N 可能為 num1-1 = 0 或更小的防護 / guard

        dig.clear();
        vector<int> tmp;                   // 先以最低位在前收集 / collect LSB first
        if (N == 0) tmp.push_back(0);      // 0 要特別放入 / handle zero explicitly
        for (ll t = N; t > 0; t /= 10)     // 逐次取餘拆位 / peel digits with % and /
            tmp.push_back((int)(t % 10));
        dig.assign(tmp.rbegin(), tmp.rend());  // 反轉成最高位在前 / reverse to MSB first

        memset(vis, 0, sizeof(vis));       // 每次重置快取（位數會變）/ reset cache per call

        auto [c, s] = dp(0, 10, 10, true); // 起始：哨兵 last/sec、tight=true / start state
        return s;                          // 取波動度總和 / return the sum
    }

public:
    long long totalWaviness(long long num1, long long num2) {
        return f(num2) - f(num1 - 1);      // 前綴和相減取得區間結果 / prefix-sum subtraction
    }
};

複雜度 / Complexity

Time / 時間： O(L × 11 × 11 × 10)，其中 L（≤ 16）是 N 的位數。狀態數是 位置 × last × secondLast = L × 11 × 11，每個狀態內部對 d = 0..9 做 10 次轉移；tight 路徑只有單一條額外成本 O(L × 10)。整體是常數級的小數字，遠快於枚舉。The state space is pos × last × secondLast, each with 10 transitions; L ≤ 16 since N ≤ 10^15. Effectively constant time.
Space / 空間： O(L × 11 × 11) 用於記憶化陣列（cntMemo、sumMemo、vis），加上遞迴深度 O(L) 的呼叫堆疊。The memo tables plus an O(L) recursion stack.

Pitfalls & Edge Cases

整數溢位 / Overflow： num2 可達 10^15，數量與波動度總和都超過 32 位元 int 的範圍。必須用 64 位元（long long）儲存參數、回傳值、以及 DP 的 count/sum，否則結果會錯。Use long long everywhere; int overflows.
前導零誤判 / Leading zeros as fake neighbors： 若直接把短數字補零當成真實數位，會把補上的 0 當成鄰居而誤判峰谷（例如把 7 看成 07 可能出錯）。本解用哨兵 10 標記「尚無真實數位」，並要求 sec != 10 才判斷，徹底避開此陷阱。The sentinel 10 plus the sec != 10 guard prevent padded zeros from counting as neighbors.
嚴格大於/小於 / Strict comparison： 峰谷的定義是「嚴格」大於或小於兩邊。相等的情況（如 4 8 8 中的 8）兩邊不嚴格，不算峰也不算谷。程式用 > 與 <（非 >=/<=）正確實作。Use strict </>; equal neighbors form neither peak nor valley.
f(num1 − 1) 的邊界 / Lower-bound edge： 當 num1 = 1 時 num1 − 1 = 0，f 必須能正確處理 N = 0（程式特別把 0 放進位數陣列）。同時 N < 0 直接回傳 0 作為保險。f handles N = 0 and guards N < 0.
首位與末位不可為峰谷 / First and last digits excluded： 演算法天然滿足此規則——最高位放下時 sec == 10（無左鄰）故跳過；最低位放下後沒有任何後續數字去當它的右鄰，因此永不被判斷。This falls out naturally from the DP structure, no special case needed.
快取的重置 / Resetting the cache between calls： f(num2) 與 f(num1−1) 兩數位數可能不同，DP 結果不可共用。每次 f 都 memset 清空 vis，避免用到上一次的舊值。Clear the memo each f call since lengths differ.