给你一个长度为n的整数数组nums和一个整数k。对于每个下标i定义它的不稳定值为max(nums[0..i - 1]) - min(nums[i..n - 1])。换句话说max(nums[0..i - 1])表示从下标 0 到下标i - 1的元素中的最大值。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 1000 nums[i] 10^90 k 10^9分析先分别求出最大值和最小值数组再从小到大遍历所有下标检查是否存在一个下标的不稳定值小于等于 k 即可。int firstStableIndex(int* nums, int numsSize, int k) { int cnt_max[numsSize],cnt_min[numsSize]; for(int i0,jnumsSize-1;inumsSize;i,--j) { if(i0)cnt_max[i]nums[i],cnt_min[j]nums[j]; else cnt_max[i]fmax(cnt_max[i-1],nums[i]),cnt_min[j]fmin(cnt_min[j1],nums[j]); } for(int i0;inumsSize;i) if(cnt_max[i]-cnt_min[i]k)return i; return -1; }
