LeetCode 解題筆記：3904. Smallest Stable Index II

作者：王一哲
日期：2026年9月5日


LeetCode 題目連結：3904. Smallest Stable Index II

解題想法

中等難度題，3903. Smallest Stable Index I 的加強版，題目的敘述及要求都一樣，但是測資範圍變大，改成 $1 \leq nums.length \leq 10^5, 0 \leq nums[i] \leq 10^9, 0 \leq k \leq 10^9$，基本上用前一篇 LeetCode 解題筆記：3903. Smallest Stable Index I 的寫法就能通過，只需要將 C 語言程式碼中的 $rmin$ 長度開成 $100001$ 就好。

Python 程式碼

Runtime: 127 ms, beats 91.82%. Memory: 33.26 MB, beats 23.64%.

class Solution:
    def firstStableIndex(self, nums: list[int], k: int) -> int:
        n = len(nums)  # 數量
        # 由右向左找每個位置的最小值
        rmin = [0] * n  # 每個索引值對應的右側最小值
        curr = float('inf')  # 目前的右側最小值
        for i in range(n-1, -1, -1):
            curr = min(curr, nums[i])
            rmin[i] = curr
        # 由左向右找 stable index
        lmax = 0  # 目前的左側最大值
        for i in range(n):
            lmax = max(lmax, nums[i])
            if lmax - rmin[i] <= k:
                return i
        return -1

C++ 程式碼

Runtime: 6 ms, beats 80.60%. Memory: 202.54 MB, beats 85.02%.

class Solution {
public:
    int firstStableIndex(vector<int>& nums, int k) {
        int n = (int)nums.size(), curr = 1000000000;
        vector<int> rmin (n, 0);
        for(int i = n-1; i >= 0; i--) {
            curr = min(curr, nums[i]);
            rmin[i] = curr;
        }
        int lmax = 0;
        for(int i = 0; i < n; i++) {
            lmax = max(lmax, nums[i]);
            if (lmax - rmin[i] <= k) {
                return i;
            }
        }
        return -1;
    }
};

C 語言程式碼

Runtime: 11 ms, beats 25.00%. Memory: 22.20 MB, beats 100.00%.

int firstStableIndex(int* nums, int numsSize, int k) {
    // 由右到左，找這個位置及其右側的最小值
    int curr = 10000000000, rmin[100001] = {0};
    for(int i = numsSize - 1; i >= 0; i--) {
        if (nums[i] < curr) curr = nums[i];
        rmin[i] = curr;
    }

    // 從左到右找目前的左側最大值 lmax，如果 lmax - rmin[i] <= k，回傳 i
    int lmax = 0;
    for(int i = 0; i < numsSize; i++) {
        if (nums[i] > lmax) lmax = nums[i];
        if (lmax - rmin[i] <= k) return i;
    }
    return -1;  // 沒有找到，回傳 -1
}