3903.最小稳定下标 I：O(n^2)或O(n)

【LetMeFly】3903.最小稳定下标 I：O(n^2)或O(n)

力扣题目链接：https://leetcode.cn/problems/smallest-stable-index-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 的不稳定值 小于等于 k，则称该下标为 稳定下标 。

返回 最小 的稳定下标。如果不存在这样的下标，则返回 -1。

 

示例 1：

输入： nums = [5,0,1,4], k = 3

输出： 3

解释：

  • 在下标 0 处：[5] 中的最大值是 5，[5, 0, 1, 4] 中的最小值是 0，因此不稳定值为 5 - 0 = 5。
  • 在下标 1 处：[5, 0] 中的最大值是 5，[0, 1, 4] 中的最小值是 0，因此不稳定值为 5 - 0 = 5。
  • 在下标 2 处：[5, 0, 1] 中的最大值是 5，[1, 4] 中的最小值是 1，因此不稳定值为 5 - 1 = 4。
  • 在下标 3 处：[5, 0, 1, 4] 中的最大值是 5，[4] 中的最小值是 4，因此不稳定值为 5 - 4 = 1。
  • 这是第一个不稳定值小于等于 k = 3 的下标，因此答案是 3。

示例 2：

输入： nums = [3,2,1], k = 1

输出： -1

解释：

  • 在下标 0 处，不稳定值为 3 - 1 = 2。
  • 在下标 1 处，不稳定值为 3 - 1 = 2。
  • 在下标 2 处，不稳定值为 3 - 1 = 2。
  • 这些值都不小于等于 k = 1，因此答案是 -1。

示例 3：

输入： nums = [0], k = 0

输出： 0

解释：

在下标 0 处，不稳定值为 0 - 0 = 0，它小于等于 k = 0。因此答案是 0。

 

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 109
  • 0 <= k <= 109

解题方法一：模拟

从前到后遍历$nums$数组，对于下标$i$，从$0$到$i$遍历求最大值，从$i$到$n-1$遍历求最小值，若二者之差$\leq k$，则直接返回下标$i$。

若遍历完成未返回则返回$-1$。

  • 时间复杂度$O(len(nums)^2)$
  • 空间复杂度$O(1)$

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/*
 * @LastEditTime: 2026-09-04 18:34:14
 */
class Solution {
private:
    int getM(vector<int>& nums, int i) {
        int ans = nums[0];
        for (int j = 0; j <= i; j++) {
            ans = max(ans, nums[j]);
        }
        return ans;
    }

    int getm(vector<int>& nums, int i) {
        int ans = nums[i];
        for (; i < nums.size(); i++) {
            ans = min(ans, nums[i]);
        }
        return ans;
    }
public:
    int firstStableIndex(vector<int>& nums, int k) {
        for (int i = 0, n = nums.size(); i < n; i++) {
            if (getM(nums, i) - getm(nums, i) <= k) {
                return i;
            }
        }
        return -1;
    }
};

解题方法二：前后缀分解（类似前缀和）

倒序遍历一遍$nums$数组，得到“后续最小值数组”$mini$，其中$mini[i]$表示从下标$i$到下标$n-1$的最小值。

再从前到后遍历$nums$数组，同时维护一个遍历过程中的最大值$M$，若$M-mini[i]\leq k$，则直接返回下标$i$。

若遍历完成未返回则返回$-1$。

  • 时间复杂度$O(len(nums))$
  • 空间复杂度$O(len(nums))$

由于本题数据量较小，所以实际上方法一的平均开销更低。

AC代码

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
 * @LastEditTime: 2026-09-04 18:38:35
 */
class Solution {
public:
    int firstStableIndex(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> mini(n);
        mini.back() = nums.back();
        for (int i = n - 2; i >= 0; i--) {
            mini[i] = min(nums[i], mini[i + 1]);
        }
        for (int i = 0, M = 0; i < n; i++) {
            M = max(M, nums[i]);
            if (M - mini[i] <= k) {
                return i;
            }
        }
        return -1;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源