lao1 me
搜索
首页/AI

Leetcode每日一题 —— 3903. 最小稳定下标 I

158
  • 魔法师
    魔法师2026-09-04
    13093

    力扣 LeetCode

    图片

    3903. 最小稳定下标 I - 力扣（LeetCode）

    3903. 最小稳定下标 I - 给你一个长度为 n 的整数数组 nums 和一个整数 k。

    对于每个下标 i，定义它的 不稳定值 为 max(nums[0..i]) - min(nums[i..n - 1])。

    换句话说：

    • max(nums[0..i]) 表示从下标 0 到下标 i 的元素中的 最大值 。
    • min(nums[i..n - 1]) 表示从下标 i 到下标 n - 1 的元素中的 最小值 。

    如果某个下标 i 的不稳定值 小于等于...

    思路

    依旧简单题。先从前到后计算出当前坐标左侧最大值，然后从后到前计算出当前坐标右侧最小值，如果稳定则更新结果为当前坐标。

    嗯，好像反过来能更快些 ^-^

    代码```
    class Solution {
    public int firstStableIndex(int[] nums, int k) {
    int n = nums.length;
    int[] mx = new int[n];
    mx[0] = nums[0];
    for (int i = 1; i < n; i++) {
    mx[i] = Math.max(mx[i - 1], nums[i]);
    }
    int ans = -1;
    int mn = Integer.MAX_VALUE;
    for (int i = n - 1; i >= 0; i--) {
    mn = Math.min(mn, nums[i]);
    if (mx[i] - mn <= k) {
    ans = i;
    }
    }
    return ans;
    }
    }

    主楼
  • Lvvvv
    Lvvvv2026-09-04
    17266
    class Solution {
public:
    int firstStableIndex(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> suf_min(n,0);
        suf_min[n - 1] = nums[n - 1];
        for(int i = n - 2; i >= 0; i--) {
            suf_min[i] = min(suf_min[i + 1],nums[i]);
        }
        int pre_max = 0;
        for(int i = 0; i < n; i++) {
            pre_max = max(pre_max,nums[i]);
            auto instable = pre_max - suf_min[i];
            if(instable <= k) {
                return i;
            }
        }
        return -1;
    }
};
    #1
  • SomeBottle
    SomeBottle2026-09-04
    11179

    预生成后缀最小值，动态更新前缀最大值并找到符合题目要求的下标即可。```
    class Solution {
    public:
    int firstStableIndex(vector<int>& nums, int k) {
    // 不稳定值是前缀最大值 - 后缀最小值
    // 预先生成后缀最大值即可
    int n=nums.size();
    vector<int> postMin(n);
    postMin[n-1]=nums[n-1];
    for(int i=n-2;i>=0;i--){
    postMin[i]=min(nums[i],postMin[i+1]);
    }
    int preMax=nums[0];
    // 扫描到第一个满足不稳定值 <=k 的下标为止
    for(int i=0;i<n;i++){
    preMax=max(preMax,nums[i]);
    if(preMax-postMin[i]<=k){
    return i;
    }
    }
    return -1;
    }
    };

    #2
  • o8080x
    o8080x2026-09-04
    28632

    Kotlin每日打卡（前缀和/前后缀分解）：```
    class Solution {
    fun firstStableIndex(nums: IntArray, k: Int): Int {
    val n = nums.size
    var maxValue = Int.MIN_VALUE
    val minValues = IntArray(n) { nums.last() }
    for (i in (n - 2) downTo 0) {
    minValues[i] = minOf(nums[i], minValues[i + 1])
    }

    for (i in 0..<n) {
    maxValue = maxOf(maxValue, nums[i])
    if (maxValue - minValues[i] <= k) {
    return i
    }
    }
    return -1
    }
    }

    #3
  • 欧拉线
    欧拉线2026-09-04
    12619

    C语言版本```
    int firstStableIndex(int* nums, int numsSize, int k) {
    if (numsSize <= 0)
    return -1;
    int ans = 0;
    int prefixMax = nums[0];
    int candidateMax = nums[0];
    for (int j = 0; j < numsSize; ++j) {
    if (nums[j] > prefixMax)
    prefixMax = nums[j];
    // ans 是新的候选下标，记录 max(nums[0..ans])
    if (j == ans)
    candidateMax = prefixMax;
    // nums[j] 使当前候选不稳定，直接跳过 [ans, j]
    if (j >= ans && (long long)candidateMax - nums[j] > (long long)k) {
    ans = j + 1;
    }
    }
    return ans < numsSize ? ans : -1;
    }

    #4
  • attention1111
    attention11112026-09-04
    8421
    class Solution:
    def firstStableIndex(self, nums: list[int], k: int) -> int:
        n=len(nums)
        for i in range(n):
            maxnum=max(nums[:i+1])
            minnum=min(nums[i:])
            if maxnum-minnum<=k:
                return i 
        return -1
    #5
  • doge
    doge2026-09-04
    28633

    非常简单 ^-^```
    class Solution:
    def firstStableIndex(self, nums: list[int], k: int) -> int:
    n = len(nums)

    suf = [inf] * n
    suf[-1] = nums[-1]
    for i in range(n - 2, -1, -1):
    suf[i] = min(suf[i + 1], nums[i])

    pre = -inf
    for i in range(n):
    pre = max(pre, nums[i])
    if pre - suf[i] <= k:
    return i

    return -1

    #6
  • CPython
    CPython2026-09-04
    14995

    被样例误导,看错了,一开始看成i-1了,导致疯狂的wa,```
    class Solution:
    def firstStableIndex(self, nums: list[int], k: int) -> int:
    mx = nums[0]
    n = len(nums)
    mi = [nums[-1]] * (n+1)
    for i in range(n-1, -1, -1):
    mi[i] = min(mi[i+1], nums[i])

    for i in range(n):
    if (mx - mi[i]) <= k:
    return i
    if nums[i] > mx:
    mx = nums[i]
    return -1

    #7
  • CPython
    CPython2026-09-04
    14995

    我突然发现我这个如果做明天的题会WA掉,判断最大值有一个地方会存在漏洞， 就是我是先比较再维护,这样的话是有问题的,不过样例集中缺少这个样例,比如```
    nums = [6,3,2,0,4,10,5], k = 1
    ```这个时候是有问题的,

    更新代码:```
    class Solution:
    def firstStableIndex(self, nums: list[int], k: int) -> int:
    mx = nums[0]
    n = len(nums)
    mi = [nums[-1]] * (n+1)
    for i in range(n-1, -1, -1):
    mi[i] = min(mi[i+1], nums[i])

    for i in range(n):
    if nums[i] > mx:
    mx = nums[i]
    if (mx - mi[i]) <= k:
    return i
    return -1

    #8

发表回复

登录后回复