LeetCode 解題筆記：3903. Smallest Stable Index I

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


LeetCode 題目連結：3903. Smallest Stable Index I

解題想法

簡單題。題目給一個長度為 $n$ 的陣列 $nums$ 及整數 $k$，如果索引值 $i$ 符合 $max(nums[0..i]) - min(nums[0..n-1]) \leq k$，則 $i$ 是穩定的 (stable)，題目要找出最小的穩定索引值。先建立一個陣列 $rmin$，$rmin[i]$ 為 $i$ 到 $n-1$ 之中的最小值，再由左到右找 $0$ 到 $i$ 的最大值 $lmax$，如果 $lmax - rmin[i] \leq k$ 回傳 $i$，如果最後沒有找到符合條件的索引值則回傳 $-1$。

Python 程式碼

Runtime: 0 ms, beats 100.00%. Memory: 19.22 MB, beats 71.43%.

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: 0 ms, beats 100.00%. Memory: 31.23 MB, beats 46.94%.

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: 4 ms, beats 12.50%. Memory: 10.57 MB, beats 9.38%.

int firstStableIndex(int* nums, int numsSize, int k) {
    // 由右到左，找這個位置及其右側的最小值
    int curr = 10000000000, rmin[101] = {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
}