目标
给你一个长度为 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 <= 10^5
- 0 <= nums[i] <= 10^9
- 0 <= k <= 10^9
思路
与 3903.最小稳定下标I 相比数据范围扩大了。
代码
/**
* @date 2026-09-07 9:01
*/
public class FirstStableIndex3904 {
public int firstStableIndex(int[] nums, int k) {
int n = nums.length;
int[] suffix = new int[n + 1];
Arrays.fill(suffix, Integer.MAX_VALUE);
for (int i = n - 1; i >= 0; i--) {
suffix[i] = Math.min(suffix[i + 1], nums[i]);
}
int max = 0;
for (int i = 0; i < n; i++) {
max = Math.max(max, nums[i]);
if (max - suffix[i] <= k) {
return i;
}
}
return -1;
}
}
性能
