2. Linux.do
  3. Leetcode每日一题 —— 3904. 最小稳定下标 II

Leetcode每日一题 —— 3904. 最小稳定下标 II

魔法师 2026-09-05 09:21 1


思路


嗯。。。题目跟昨天一样，只是增大了范围。

昨天的代码就能过，不过今天改为 先从后到前计算出当前坐标右侧最小值，然后从后到前计算出当前坐标左侧最大值，如果稳定值就返回结果。这样可以提前返回结果，比昨天的代码快一点。


代码


class Solution {

    public int firstStableIndex(int[] nums, int k) {

        int n = nums.length;

        int[] mn = new int[n];

        mn[n - 1] = nums[n - 1];

        for (int i = n - 2; i >= 0; i--) {

            mn[i] = Math.min(mn[i + 1], nums[i]);

        }

        int mx = Integer.MIN_VALUE;

        for (int i = 0; i < n; i++) {

            mx = Math.max(mx, nums[i]);

            if (mx - mn[i] <= k) {

                return i;

            }

        }

        return -1;

    }

}
最新回复 (4)
  • SomeBottle 09-05 09:30
    1楼

    和昨天那题唯一的区别是输入规模变大，无法暴力了。


    class Solution {
    
public:
    
    int firstStableIndex(vector<int>& nums, int k) {
    
        // 和最小稳定下标 I 的区别就是数值范围更大
    
        int n=nums.size();
    
        int preMax=nums[0];
    
        vector<int> postMin(n);
    
        postMin[n-1]=nums[n-1];
    
        for(int i=n-2;i>=0;i--){
    
            postMin[i]=min(postMin[i+1],nums[i]);
    
        }
    
        for(int i=0;i<n;i++){
    
            preMax=max(preMax,nums[i]);
    
            if(preMax-postMin[i]<=k){
    
                return i;
    
            }
    
        }
    
        return -1;
    
    }
    
};
  • attention1111 09-05 09:36
    2楼

    我昨天的直接超时


    class Solution:
    
    def firstStableIndex(self, nums: list[int], k: int) -> int:
    
        n=len(nums)
    
        minnum,maxnum=nums[n-1],nums[0]
    
        minnums=[0]*n
    
        for i in range(n-1,-1,-1):
    
            minnum=min(minnum,nums[i])
    
            minnums[i]=minnum
    
        for i in range(n):
    
            maxnum=max(maxnum,nums[i])
    
            if maxnum-minnums[i]<=k:
    
                return i 
    
        return -1
  • o8080x 09-05 10:48
    3楼

    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 
    
    }
    
}
  • Lvvvv 09-05 12:30
    4楼

    一样。


    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;
    
    }
    
};
* 帖子来源Linux.do
附近帖子
返回
飞读
随机推荐