3536. Maximum Product of Two Digits

題目 / Problem

中文： 給你一個正整數 n。請回傳 n 的任意兩個數字（digit）相乘所能得到的最大乘積。注意：如果某個數字在 n 中出現超過一次，你可以重複使用它；即使只是同一個數字位出現兩次（例如 22），也算兩個不同的位置。

English: You are given a positive integer n. Return the maximum product of any two digits in n. Note: you may use the same digit twice if it appears more than once in n (each digit position counts separately, so 22 gives 2 * 2 = 4).

Constraints / 限制： - 10 <= n <= 10^9 — so n always has at least two digits, and at most 10 digits.

Worked example / 範例： n = 124 → digits are [1, 2, 4]. Products: 1*2=2, 1*4=4, 2*4=8. The maximum is 8.

名詞解釋 / Glossary

• digit / 數字位：整數中的單一個位數，範圍是 0–9。例如 124 的數字位是 1、2、4。
• modulo % / 取餘數：n % 10 會取出 n 的個位數（最右邊那位）。例如 124 % 10 = 4。這是拆數字最常用的技巧。
• integer division / / 整數除法：在 C/C++ 中，兩個整數相除會捨去小數。n / 10 會把最右邊那位「切掉」。例如 124 / 10 = 12。
• greedy / 貪心法：不用嘗試所有組合，只要抓住「最大」與「次大」兩個數字即可，因為乘積要最大，一定用這兩個最大的。
• brute force / 暴力法：把每一對數字都乘一遍，取最大值。資料量很小時完全夠用。

思路

中文： 最直接的想法是暴力法：先把 n 的每一位數字拆出來存進一個陣列，然後用兩層迴圈試遍每一對 (i, j)（其中 i < j），計算乘積並記錄最大值。由於 n 最多只有 10 位數字，最多也只有約 45 對組合，這個做法完全夠快，符合題目「Use brute force」的提示。

不過我們可以看得更清楚：要讓乘積最大，一定是挑出最大的數字和次大的數字相乘（因為所有數字都是非負數，兩個最大的相乘必定最大）。所以更聰明的貪心法是：邊拆數字邊維護兩個變數 max1（最大）和 max2（次大）。每拆出一位 d，如果 d 比 max1 大，就把舊的 max1 降級成 max2，再讓 max1 = d；否則如果 d 只比 max2 大，就更新 max2。掃完所有位數後，答案就是 max1 * max2。這個方法只需掃一遍、用常數空間，且不需要陣列。因為題目保證至少兩位數，max1 和 max2 一定都會被賦上真正的數字，不必擔心少於兩個數字的情況。

English: The most direct idea is brute force: extract every digit of n into an array, then use two nested loops over each pair (i, j) with i < j, multiply them, and track the maximum. Since n has at most 10 digits, there are at most ~45 pairs — plenty fast, exactly what the "Use brute force" hint suggests.

But we can do even cleaner. To maximize a product of two non-negative digits, you simply want the largest digit times the second-largest digit. So the greedy approach keeps two running variables while peeling off digits: max1 (largest so far) and max2 (second largest). For each digit d: if d > max1, the old max1 gets demoted to max2 and max1 becomes d; otherwise if d > max2, update max2. After processing all digits, the answer is max1 * max2. This runs in a single pass with constant space — no array needed. Because the constraints guarantee at least two digits, both max1 and max2 are always filled with real digits, so we never hit an "only one digit" edge case.

逐步走查 / Walkthrough

Example / 範例：n = 124. We peel digits from the right using % 10 and / 10, updating max1 and max2.

Start / 初始：max1 = 0, max2 = 0.

Loop ends when n becomes 0 / 當 n 變成 0 時迴圈結束。

Answer / 答案：max1 * max2 = 4 * 2 = 8. ✓

Solution — C

// 演算法：邊用 %10 和 /10 拆出每一位數字，邊維護最大值 max1 與次大值 max2，
// 最後回傳 max1 * max2。單次掃描、常數空間。
// Algorithm: peel each digit with %10 and /10 while tracking the largest (max1)
// and second-largest (max2) digit; return max1 * max2. Single pass, O(1) space.
int maxProduct(int n) {
    int max1 = 0;                 // 目前最大的數字 / the largest digit seen so far
    int max2 = 0;                 // 目前次大的數字 / the second-largest digit so far

    while (n > 0) {               // 只要還有位數沒處理就繼續 / loop until all digits consumed
        int d = n % 10;          // 取出最右邊那位 / grab the rightmost digit (units place)

        if (d > max1) {          // 新數字比目前最大還大 / d beats the current maximum
            max2 = max1;         // 舊的最大降級為次大 / old max1 becomes the new second place
            max1 = d;            // 新數字成為最大 / d takes the top spot
        } else if (d > max2) {   // 不是最大，但比次大還大 / not the max, but beats second place
            max2 = d;            // 更新次大 / update the runner-up
        }

        n /= 10;                 // 切掉最右邊那位，往左移一位 / drop the processed digit
    }

    return max1 * max2;          // 最大兩位相乘即為答案 / product of the top two digits
}

Solution — C++

// 演算法與 C 版相同：用 %10 / /10 拆數字，維護 max1（最大）與 max2（次大），
// 回傳 max1 * max2。這裡用 std::max 讓程式更簡潔。
// Same algorithm as the C version: peel digits with %10 and /10, keep max1 and max2,
// return max1 * max2. Uses std::max for a cleaner style.
class Solution {
public:
    int maxProduct(int n) {
        int max1 = 0, max2 = 0;      // 最大、次大數字 / largest and second-largest digit
        while (n > 0) {              // 逐位處理，直到 n 變 0 / process each digit until n hits 0
            int d = n % 10;          // 取出個位數 / extract the units digit
            if (d > max1) {          // d 超越目前最大 / d is a new maximum
                max2 = max1;         // 原最大退為次大 / demote old max to second place
                max1 = d;            // d 成為新最大 / d becomes the new max
            } else {                 // 否則只可能更新次大 / otherwise it can only affect second place
                max2 = std::max(max2, d);  // 取 max2 與 d 的較大者 / keep the larger of the two
            }
            n /= 10;                 // 移除已處理的個位 / chop off the processed digit
        }
        return max1 * max2;          // 頂端兩個數字的乘積 / product of the top two digits
    }
};

複雜度 / Complexity

• Time / 時間： O(log₁₀ n) — 迴圈次數等於 n 的位數，而位數約為 log₁₀ n；因為 n ≤ 10^9，最多只跑 10 次，實務上等同常數。The loop runs once per digit, and the number of digits is ~log₁₀ n (at most 10 here), so it's effectively constant.
• Space / 空間： O(1) — 只用了 max1、max2、d 幾個變數，不隨輸入大小增長。Only a few scalar variables are used; no array or extra structure grows with the input.

Pitfalls & Edge Cases

• 只用一個變數找最大是不夠的 / Tracking only one maximum is not enough. 你需要兩個變數（最大與次大），否則像 124 你會漏掉第二大的數字。The whole problem is about two digits, so a single max variable can't produce the answer.
• 降級順序不能寫反 / Order matters when demoting. 在 d > max1 分支裡，必須先做 max2 = max1 再做 max1 = d；反過來會讓 max2 拿到新值而不是舊的最大值。Assigning max1 = d before max2 = max1 would corrupt max2.
• 重複數字是允許的 / Duplicate digits are allowed. 像 22 應回傳 4。此解法自然支援：第一個 2 設成 max1，第二個 2 因為 2 > max2(0) 而設成 max2。The algorithm handles this correctly with no special case.
• 初始值設 0 是安全的 / Initializing to 0 is safe. 因為題目保證 n ≥ 10（至少兩位數），max1 與 max2 一定會被真實數字覆蓋；就算真的出現 0，它也不會讓乘積偏大。The n ≥ 10 constraint guarantees both variables get filled by real digits.
• 不會溢位 / No overflow risk. 最大乘積是 9 * 9 = 81，遠在 int 範圍內。The product never exceeds 81, so int is more than sufficient.