You are given an integer array nums of length n and an integer k.
For each index i, define its instability score as max(nums[0..i]) - min(nums[i..n - 1]).
In other words:
max(nums[0..i]) is the largest value among the elements from index 0 to index i.min(nums[i..n - 1]) is the smallest value among the elements from index i to index n - 1.An index i is called stable if its instability score is less than or equal to k.
Return the smallest stable index. If no such index exists, return -1.
Example 1:
Input: nums = [5,0,1,4], k = 3
Output: 3
Explanation:
[5] is 5, and the minimum in [5, 0, 1, 4] is 0, so the instability score is 5 - 0 = 5.[5, 0] is 5, and the minimum in [0, 1, 4] is 0, so the instability score is 5 - 0 = 5.[5, 0, 1] is 5, and the minimum in [1, 4] is 1, so the instability score is 5 - 1 = 4.[5, 0, 1, 4] is 5, and the minimum in [4] is 4, so the instability score is 5 - 4 = 1.k = 3. Thus, the answer is 3.Example 2:
Input: nums = [3,2,1], k = 1
Output: -1
Explanation:
3 - 1 = 2.3 - 1 = 2.3 - 1 = 2.k = 1, so the answer is -1.Example 3:
Input: nums = [0], k = 0
Output: 0
Explanation:
At index 0, the instability score is 0 - 0 = 0, which is less than or equal to k = 0. Therefore, the answer is 0.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1090 <= k <= 109class Solution {
public int firstStableIndex(int[] nums, int k) {
int n = nums.length, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
int[] instability = new int[n];
for (int i = 0; i < n; i++) {
instability[i] += max = Math.max(max, nums[i]);
instability[n - 1 - i] -= min = Math.min(min, nums[n - 1 - i]);
}
// System.out.println(Arrays.toString(prefMax));
// System.out.println(Arrays.toString(suffMin));
for (int i = 0; i < n; i++)
if (instability[i] <= k)
return i;
return -1;
}
}