3660. Jump Game IX

題目 / Problem

中文： 給定整數陣列 nums。從任一索引 i 出發，你可以依以下規則跳到另一索引 j： - 向前跳（j > i）：只有當 nums[j] < nums[i] 才允許。 - 向後跳（j < i）：只有當 nums[j] > nums[i] 才允許。

對每個索引 i，求出從 i 出發、經過任意次合法跳躍後可到達的 nums 中的最大值。回傳陣列 ans，其中 ans[i] 為從 i 出發可達的最大值。

English: Given an integer array nums. From any index i, you may jump to another index j under: - Forward (j > i): allowed only if nums[j] < nums[i]. - Backward (j < i): allowed only if nums[j] > nums[i].

For each i, find the maximum value in nums reachable through any sequence of valid jumps starting at i. Return ans where ans[i] is that maximum.

Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^9.

Example: nums = [2,3,1] → ans = [3,3,3]. From index 0 (value 2) we can jump forward to index 2 (value 1 < 2), then jump backward to index 1 (value 3 > 1). So everyone reaches 3.

名詞解釋 / Glossary

• 連通分量 / Connected component：把每個合法跳躍當作一條有向邊，所有能互相到達的索引組成一個分量。本題中可以證明分量一定是連續區間。Each index is a node; valid jumps are edges. A connected component is the set of mutually reachable indices — and here they are always contiguous ranges.
• 前綴最大值 / Prefix max：prefMax[i] = max(nums[0..i])。從左掃到 i 為止見過的最大值。The largest value seen from the start up to index i.
• 後綴最小值 / Suffix min：sufMin[i] = min(nums[i..n-1])。從 i 到結尾的最小值。The smallest value from index i to the end.
• 切點 / Cut：兩相鄰索引 i, i+1 之間若滿足 prefMax[i] <= sufMin[i+1]，則左側所有值 ≤ 右側所有值，無論直接或間接都不能跨越，是分量的邊界。A boundary where every value on the left is ≤ every value on the right; no jump (direct or chained) can cross it.
• 就地寫入 / In-place fill：對每個分量 [left, right]，把該段最大值寫進 ans[left..right]。Once a component is closed, fill its answer slice with the component's max.
• malloc / free：C 中動態配置與釋放堆積記憶體的標準函式。Standard C heap allocation and deallocation.
• std::vector / std::min / std::max：C++ STL 中的動態陣列與比較函式。STL dynamic array and helper comparison functions.

思路

暴力做法是把每個索引當起點，做 BFS / DFS 走遍所有合法跳躍，但邊數最壞可達 O(n²)，再對每個起點各跑一次就是 O(n³)，在 n = 10⁵ 下完全跑不動。所以要找跳躍的結構。觀察兩個相鄰索引 i, i+1：若 nums[i] > nums[i+1]，可從 i 向前跳到 i+1，也可從 i+1 向後跳回 i，兩者必同分量。更一般地，考慮位置 i 和 i+1 中間的「切口」：若左半段最大值嚴格大於右半段某個值，那左半段那個高峰可以直接向前跳到右半段那個低谷（j > i、nums[j] < nums[i]），於是兩半連通；反之，若 prefMax[i] <= sufMin[i+1]，則左邊任何值都不大於右邊任何值，向前跳要求嚴格遞減、向後跳要求嚴格遞增，兩種跨越方向都被堵死，這裡就是真正的分量邊界。所以演算法只要：(1) 預先算 sufMin；(2) 從左到右掃一次同時維護 prefMax = M；(3) 一旦走到結尾或當前 M <= sufMin[i+1] 就把區間 [left, i] 的答案全填成 M，然後重置 left, M。每個位置的答案就是它所在分量的最大值，也就是該分量結束時的 prefMax。

A brute-force BFS from every index over a graph with up to O(n²) edges is hopeless for n = 10⁵. The key structural fact is that the connected components under these jump rules are contiguous index ranges, and the cut between two ranges happens exactly where prefMax[i] <= sufMin[i+1]. Intuition: if some value on the left exceeds some value on the right, that high-on-left index can forward-jump straight to the low-on-right index, gluing the two sides together; if every left value is ≤ every right value, both forward jumps (which need a strict decrease) and backward jumps (which need a strict increase) are blocked, so nothing — direct or chained — can cross. So we precompute sufMin in one right-to-left pass, then sweep left to right tracking the running prefix max M. Whenever the cut condition fires (or we hit the end), the current group [left..i] is closed and its answer is M — the maximum value inside that component, which by definition is what every index in it can reach.

逐步走查 / Walkthrough

Trace nums = [2, 1, 3] (n = 3).

Step 1 — build sufMin (right to left):

So sufMin = [1, 1, 3].

Step 2 — sweep left to right with M = 0, left = 0:

Result: ans = [2, 2, 3] ✅

Notice the two components {0,1} (max = 2) and {2} (max = 3) emerged automatically from the cut detection.

Solution — C

// Algorithm: Components are contiguous ranges. A cut between i and i+1 occurs
// when prefMax[i] <= sufMin[i+1] (every left value <= every right value, so no
// forward/backward jump can cross). Precompute sufMin, then sweep with running
// prefMax M; close each group at every cut and fill ans[left..i] with M.
// 演算法：分量必為連續區間；當前綴最大值 ≤ 後綴最小值即為切點。

#include <stdlib.h>  // malloc/free 動態記憶體 / dynamic memory

int* maxValue(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;                                  // LeetCode 透過指標回傳長度 / LeetCode reads length back via pointer
    int* ans = (int*)malloc(sizeof(int) * numsSize);         // 配置答案陣列 / allocate answer array on heap
    int* sufMin = (int*)malloc(sizeof(int) * numsSize);      // 後綴最小值陣列 / suffix-min scratch array

    sufMin[numsSize - 1] = nums[numsSize - 1];               // 最後一格的後綴最小就是它自己 / last cell's suffix min is itself
    for (int i = numsSize - 2; i >= 0; --i) {                // 從右往左填 sufMin / fill sufMin right-to-left
        // 三元運算子 ? : 等價於 if-else，取較小者 / ternary operator picks the smaller of two
        sufMin[i] = nums[i] < sufMin[i + 1] ? nums[i] : sufMin[i + 1];
    }

    int M = 0;                                               // 當前分量目前見過的最大值（前綴最大）/ running prefix max within current group
    int left = 0;                                            // 當前分量的起點索引 / start index of current group
    for (int i = 0; i < numsSize; ++i) {                     // 由左向右掃一次 / single left-to-right sweep
        if (nums[i] > M) M = nums[i];                        // 更新前綴最大值 / update prefix max with current element
        // 切點條件：到達結尾，或 M <= 右側最小（無法跨越）/ cut: end of array, or M <= sufMin[i+1] (uncrossable)
        if (i == numsSize - 1 || M <= sufMin[i + 1]) {
            for (int k = left; k <= i; ++k) {                // 把整段 [left, i] 答案填成 M / fill whole component slice with M
                ans[k] = M;                                  // 該索引可達的最大值即此分量的最大 / max reachable from k is M
            }
            left = i + 1;                                    // 下一個分量從 i+1 開始 / next group starts after the cut
            M = 0;                                           // 重置最大值（nums[i] >= 1 安全）/ reset M (safe since nums[i] >= 1)
        }
    }

    free(sufMin);                                            // 釋放暫存陣列，避免記憶體洩漏 / free scratch buffer to avoid leak
    return ans;                                              // 由 LeetCode harness 負責 free(ans) / harness frees ans
}

Solution — C++

// Algorithm: Same as the C version. Components are contiguous; a cut sits where
// prefix-max meets suffix-min with prefMax[i] <= sufMin[i+1]. One sweep with a
// running max M; on each cut, write M into ans[left..i] and reset.
// 演算法同 C 版本：用前綴最大與後綴最小定位切點，分量內每格答案都是該段最大。

#include <vector>     // std::vector 動態陣列 / dynamic array container
#include <algorithm>  // std::min, std::max

class Solution {
public:
    std::vector<int> maxValue(std::vector<int>& nums) {
        int n = static_cast<int>(nums.size());               // 取陣列長度，轉成 int 比較好用 / cast size to int for index math
        std::vector<int> sufMin(n);                          // 後綴最小值陣列，長度 n / suffix-min array of length n

        sufMin[n - 1] = nums[n - 1];                         // 最右端的後綴最小是自己 / rightmost suffix min is itself
        for (int i = n - 2; i >= 0; --i) {                   // 從右往左填 / fill right-to-left
            // std::min 取兩數較小，較三元運算子更可讀 / std::min returns the smaller of two values
            sufMin[i] = std::min(nums[i], sufMin[i + 1]);
        }

        std::vector<int> ans(n);                             // 結果陣列，預設值 0 / result vector, default-initialised to 0
        int M = 0;                                           // 當前分量的前綴最大 / running prefix max in current group
        int left = 0;                                        // 當前分量的左端索引 / left boundary of current group
        for (int i = 0; i < n; ++i) {                        // 範圍迴圈也可，這裡需要索引 / index-based loop because we need i
            M = std::max(M, nums[i]);                        // 更新前綴最大 / update running max
            // 切點：i 是最後一個元素，或前綴最大 <= 後綴最小（左邊全部 <= 右邊全部，跨不過去）
            // Cut: end of array, or every left value <= every right value (no jump can bridge them).
            if (i == n - 1 || M <= sufMin[i + 1]) {
                for (int k = left; k <= i; ++k) {            // 把整段答案填成 M / write component max into the slice
                    ans[k] = M;
                }
                left = i + 1;                                // 下一段從 i+1 開始 / next component starts after the cut
                M = 0;                                       // 重置（nums[i] >= 1 故安全）/ reset (safe since nums[i] >= 1)
            }
        }
        return ans;                                          // vector 會自行管理記憶體 / vector handles its own memory
    }
};

複雜度 / Complexity

• Time: O(n) — 一次右到左掃 sufMin，一次左到右主掃。看似巢狀的「填 ans[left..i]」內迴圈總共只會把每個索引寫入一次（每個位置只屬於一個分量），所以全部加起來仍是 O(n)。One pass to build sufMin, one main pass; the inner fill writes each index exactly once across all iterations because every position belongs to a single component.
• Space: O(n) — sufMin 用了一個長度 n 的輔助陣列；輸出 ans 不計入額外空間。Auxiliary sufMin array of size n; the output ans doesn't count toward extra space.

Pitfalls & Edge Cases

• 單元素陣列 / Single element (n = 1)：迴圈第一次就命中 i == n-1，直接寫 ans[0] = nums[0]，正確。Loop closes immediately on the first iteration.
• 嚴格不等號 / Strict inequalities：跳躍規則用嚴格 < 與 >，等值不能跨。切點條件用 M <= sufMin[i+1]（含等號），因為相等時依舊兩種方向都被卡死。Jumps are strict, so equality at the cut still blocks any crossing — using <= is correct.
• 整數範圍 / Integer range：nums[i] <= 10^9，int (32-bit) 足夠不會溢位。No overflow with 32-bit int.
• 重置 M = 0 / Resetting M to 0：因為題目保證 nums[i] >= 1，下一個元素一定會把 M 推上去，0 是安全的哨兵。Safe sentinel because every value is ≥ 1.
• 記憶體釋放 / Memory cleanup (C only)：sufMin 是我們自己 malloc 的，必須 free；但 ans 由 LeetCode 評測收回，不要在這裡 free。Free what you alloc; leave ans for the harness.
• 誤以為要做圖搜尋 / Don't actually build the graph：邊數最壞 O(n²)，建圖+搜尋會超時與超記憶體。看穿「分量是連續區間」這個結構是本題關鍵。Building the jump graph is a trap — n² edges blows up; the structural insight (components are intervals) is what makes O(n) possible.