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

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;

    }

};

预生成后缀最小值，动态更新前缀最大值并找到符合题目要求的下标即可。

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;

    }

};

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 

    }

}

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;

}

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

非常简单 ^-^

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

被样例误导,看错了,一开始看成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

我突然发现我这个如果做明天的题会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