3751. Total Waviness of Numbers in Range I

題目 / Problem

中文： 給你兩個整數 num1 和 num2，代表一個閉區間 [num1, num2]（兩端都包含）。

一個數字的「波動度」(waviness) 定義為它所有山峰與山谷的數量總和：

• 某個數位是山峰 (peak)：它嚴格大於左右兩個相鄰數位。
• 某個數位是山谷 (valley)：它嚴格小於左右兩個相鄰數位。
• 一個數的第一位和最後一位永遠不能算山峰或山谷（因為它們只有一個鄰居）。
• 任何少於 3 位的數字，波動度為 0。

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

English: You are given two integers num1 and num2 representing 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 (they only have one neighbor).
• Any number with fewer than 3 digits has waviness 0.

Return the sum of waviness over all numbers in [num1, num2].

約束 / Constraints: - 1 <= num1 <= num2 <= 10^5

範例 / Worked example: num1 = 120, num2 = 130 → 輸出 3。 - 120：中間數位 2 比左邊 1 和右邊 0 都大，是山峰，波動度 = 1。 - 121：中間 2 同樣是山峰，波動度 = 1。 - 130：中間 3 是山峰，波動度 = 1。 - 其餘數字波動度皆為 0。 - 總和 = 1 + 1 + 1 = 3。

名詞解釋 / Glossary

• 數位 / digit：一個數字裡的單個位數。例如 4848 由 4 個數位組成：4, 8, 4, 8。
• 相鄰數位 / neighbor：某個數位緊鄰的左邊和右邊那一位。最左邊那位沒有左鄰居，最右邊那位沒有右鄰居，所以它們不參與比較。
• 山峰 / peak：嚴格大於左右兩鄰居的數位（必須兩邊都比它小）。"嚴格"代表不能相等。
• 山谷 / valley：嚴格小於左右兩鄰居的數位。
• 暴力法 / brute force：不耍花招，直接把區間內每個數字都檢查一遍。當範圍很小（這裡最多 10^5 個數）時，這是最簡單又夠快的做法。
• 取餘數與整除 / % 10 and / 10：在 C/C++ 整數運算中，n % 10 取得最後一位數字，n / 10 把最後一位去掉（整數除法自動捨去小數）。這是逐位拆解一個整數最常用的技巧。
• 陣列 / array：一塊連續的記憶體，可以用索引 arr[i] 存取第 i 個元素。我們用它暫存一個數字的所有數位。

思路

這題的關鍵觀察是資料規模非常小：num2 最多只有 10^5 = 100000。也就是說區間內最多大約 10 萬個數字，每個數字最多 6 位。最直覺的暴力法是：對 [num1, num2] 裡的每一個數 n，把它拆成一個個數位放進陣列，然後從第二位掃到倒數第二位，檢查每個中間數位是不是嚴格大於兩鄰居（山峰）或嚴格小於兩鄰居（山谷），是的話就把波動度加一。把所有數字的波動度累加起來就是答案。為什麼這樣夠快？因為總工作量大約是「數字個數 × 每個數字的位數」≈ 10 萬 × 6 = 60 萬次基本操作，對電腦來說瞬間完成，完全不需要更聰明的數位 DP。拆數位時要注意：用 % 10 和 / 10 取出來的數位是從低位到高位（反過來）的，但峰谷判斷只看「左右是否都更大／更小」，把陣列反過來看並不影響峰谷的數量，所以不用特地再翻正，但為了直覺清楚，下面的程式碼還是把數位存成正序。

The crucial observation is that the input is tiny: num2 is at most 10^5, so the range contains at most ~100,000 numbers, each with at most 6 digits. The straightforward brute force is therefore plenty fast: for every number n in [num1, num2], break it into its individual digits, store them in an array, then scan every middle digit (index 1 through length-2) and check whether it is strictly greater than both neighbors (a peak) or strictly less than both (a valley). Each such digit contributes 1 to that number's waviness; sum across all numbers for the final answer. Total work is roughly (count of numbers) × (digits per number) ≈ 100,000 × 6 = 600,000 elementary operations — instant for a computer, so no clever digit-DP is needed. When extracting digits with % 10 and / 10 you get them from least-significant to most-significant (reversed), but since peak/valley only depends on the symmetric relation "bigger/smaller than both sides," reversing the digit order does not change the count. The code below still stores digits in natural order for readability.

逐步走查 / Walkthrough

以第一個範例 num1 = 120, num2 = 130 為例。我們對每個 n 計算波動度，這裡只展示有貢獻的數字與幾個代表：

累加 / running total：120 後 = 1，121 後 = 2，130 後 = 3。最終答案 / final answer = 3。✓

Solution — C

// 演算法 / Algorithm:
// 暴力枚舉 [num1, num2] 內每個數，拆成數位後檢查每個中間數位是否為山峰或山谷，累加總數。
// Brute-force every number in [num1, num2]: split into digits, count peaks/valleys
// among the middle digits, and accumulate. n <= 1e5 so this is easily fast enough.

int totalWaviness(int num1, int num2) {
    int total = 0;                       // 累計所有數字的波動度 / running sum of waviness

    // 外層迴圈：枚舉區間內每一個整數 n / outer loop: every integer n in the range
    for (int n = num1; n <= num2; n++) {
        int digits[7];                   // 暫存數位，最多 6 位(1e5) 留一點餘裕 / buffer for digits
        int len = 0;                     // 目前數位個數 / how many digits stored so far

        // 用 %10 取最後一位、/10 去掉最後一位，逐位拆解 / extract digits one by one
        // 注意：這樣存進去是「反序」(低位在前)，但不影響峰谷計數 / stored reversed; count unaffected
        int t = n;                       // 用副本拆解，保留原本的 n / work on a copy so n stays intact
        while (t > 0) {
            digits[len] = t % 10;        // t % 10 取出最後一位數字 / lowest digit
            len = len + 1;               // 記錄又多了一位 / one more digit recorded
            t = t / 10;                  // 整數除法捨去最後一位 / drop the lowest digit
        }

        // 少於 3 位的數字波動度一定是 0，直接跳過 / fewer than 3 digits => waviness 0
        if (len < 3) continue;

        // 掃描每個「中間」數位：索引 1 到 len-2 (頭尾不算) / scan middle digits only
        for (int i = 1; i < len - 1; i++) {
            int left  = digits[i - 1];   // 左鄰居 / left neighbor
            int mid   = digits[i];       // 目前數位 / current digit
            int right = digits[i + 1];   // 右鄰居 / right neighbor

            // 山峰：嚴格大於兩鄰居 / peak: strictly greater than both neighbors
            if (mid > left && mid > right) {
                total = total + 1;       // 找到一個峰，波動度 +1 / one peak found
            }
            // 山谷：嚴格小於兩鄰居 / valley: strictly less than both neighbors
            else if (mid < left && mid < right) {
                total = total + 1;       // 找到一個谷，波動度 +1 / one valley found
            }
            // 其餘情況(含相等)不計 / everything else (including ties) contributes 0
        }
    }

    return total;                        // 回傳區間總波動度 / return the grand total
}

Solution — C++

// 演算法 / Algorithm:
// 與 C 版相同：暴力枚舉 [num1, num2]，逐位拆解每個數，統計中間數位的山峰與山谷。
// Same as the C version: brute-force the range, split each number into digits,
// and count peaks/valleys among the interior digits. n <= 1e5 keeps it fast.

class Solution {
public:
    int totalWaviness(int num1, int num2) {
        int total = 0;                           // 累計波動度 / running sum

        // range-for 不適用於數值區間，這裡用傳統 for 枚舉每個 n / classic for over the range
        for (int n = num1; n <= num2; ++n) {
            // vector<int> 是會自動管理長度的動態陣列 / dynamic array that tracks its own size
            std::vector<int> digits;

            // 逐位拆解：%10 取末位、/10 去末位 / extract digits (reversed order, fine for counting)
            for (int t = n; t > 0; t /= 10) {
                digits.push_back(t % 10);        // push_back 在尾端加入一個元素 / append one digit
            }

            int len = (int)digits.size();        // size() 回傳元素個數 / number of digits
            if (len < 3) continue;               // 少於 3 位波動度為 0 / waviness 0, skip

            // 掃描中間數位 (索引 1 .. len-2) / scan interior digits only
            for (int i = 1; i < len - 1; ++i) {
                int left  = digits[i - 1];       // 左鄰居 / left neighbor
                int mid   = digits[i];           // 當前數位 / current digit
                int right = digits[i + 1];       // 右鄰居 / right neighbor

                // 山峰或山谷都讓波動度 +1 / a peak OR a valley adds 1
                if (mid > left && mid > right)        ++total;  // 峰 / peak
                else if (mid < left && mid < right)   ++total;  // 谷 / valley
                // 相等或一上一下不計 / ties and monotone steps contribute nothing
            }
        }

        return total;                            // 回傳答案 / return the total
    }
};

複雜度 / Complexity

• Time: O((num2 − num1) · D)，其中 D 是位數（這裡 D ≤ 6，可視為常數）。我們對區間內每個數做一次拆位（O(D)）與一次掃描（O(D)）。主導項是「數字個數 × 位數」≈ 10^5 × 6。/ For each of the (num2 − num1 + 1) numbers we do O(D) work to split and scan, where D ≤ 6 is the digit count — effectively a small constant. The dominant factor is count × digits.
• Space: O(D) = O(1)。每個數字只需要一個最多 6 格的小陣列／vector，與輸入規模無關，重複使用。/ Only a tiny per-number buffer of ≤ 6 digits is needed, independent of the range size.

Pitfalls & Edge Cases

• 「嚴格」比較不可寫成 >= / <= / Use strict > and <, not >=/<=：相等的鄰居（如 122 的中間 2）既不是峰也不是谷。若誤用 >= 會把平台誤判成峰谷。程式用 > 與 < 避免此陷阱。
• 頭尾數位不算 / First and last digits never count：它們只有一個鄰居。迴圈從 i = 1 跑到 i < len - 1，自然排除了索引 0 與 len-1。
• 少於 3 位要跳過 / Skip numbers with < 3 digits：1~2 位的數沒有中間位，波動度為 0。if (len < 3) continue; 處理掉，也避免 len - 1 變成 0 導致內層迴圈不執行（其實這裡 len<3 時內層 i<len-1 也不會跑，但顯式跳過更清楚）。
• 拆位順序反向但無害 / Digits come out reversed — that's OK：% 10 由低位取到高位，但峰谷只看對稱關係，反轉序列峰谷數不變。不需要額外翻正，省一步。
• 不要修改 n 本身 / Don't mutate the loop variable：拆位時用副本 t = n，否則 n 被除到 0 會破壞外層 for 迴圈。
• 溢位無虞 / No overflow risk：num2 ≤ 10^5，總波動度最多約 10^5 × 5 < 10^6，遠在 int 範圍內，不必用 long long。