Smallest stable index:
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:
• At index 0: The maximum in [5] is 5, and the minimum in [5, 0, 1, 4] is 0, so the instability score is 5 - 0 = 5.
• At index 1: The maximum in [5, 0] is 5, and the minimum in [0, 1, 4] is 0, so the instability score is 5 - 0 = 5.
• At index 2: The maximum in [5, 0, 1] is 5, and the minimum in [1, 4] is 1, so the instability score is 5 - 1 = 4.
• At index 3: The maximum in [5, 0, 1, 4] is 5, and the minimum in [4] is 4, so the instability score is 5 - 4 = 1.
• This is the first index with an instability score less than or equal to k = 3. Thus, the answer is 3.
Example 2:
Input: nums = [3,2,1], k = 1
Output: -1
Explanation:
• At index 0, the instability score is 3 - 1 = 2.
• At index 1, the instability score is 3 - 1 = 2.
• At index 2, the instability score is 3 - 1 = 2.
• None of these values is less than or equal to 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 <= 100
• 0 <= nums[i] <= 109
• 0 <= k <= 109
class Solution {
public int firstStableIndex(int[] nums, int k) {
long[] scores = new long[nums.length];
for (int i = 0; i < nums.length; i++) {
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int j = 0; j <= i; j++) {
if (nums[j] > max) {
max = nums[j];
}
}
for (int j = i; j < nums.length; j++) {
if (nums[j] < min) {
min = nums[j];
}
}
// System.out.println("max="+max+"&min="+min);
scores[i] = (long) max - min;
}
long min_score = k;
int min_score_index = -1;
int first_stable_index = Integer.MIN_VALUE;
for (int i = 0; i < scores.length; i++) {
if ( scores[i] <= min_score ) {
min_score = scores[i];
min_score_index = i;
if (first_stable_index == Integer.MIN_VALUE) {
first_stable_index = i;
}
}
}
if (first_stable_index == Integer.MIN_VALUE) {
first_stable_index = -1;
}
return first_stable_index;
}
}
Test cases:
Case 1:
Input
nums =
[5,0,1,4]
k =
3
Output
3
Expected
3
Case 2:
Input
nums =
[3,2,1]
k =
1
Output
-1
Expected
-1
Case 3:
Input
nums =
[0]
k =
0
Output
0
Expected
0
No comments:
Post a Comment