算法技巧合集

陆续整理一些算法技巧放在这里

范围内求最值

// f[i]在arr[:i]的最小值
int[] f = new int[n];
f[0] = nums[0];
for (int i = 1; i < n; i++) {
    f[i] = Math.min(f[i-1], nums[i]);
}

// f[i]在arr[:i]的最大值
int[] f = new int[n];
f[0] = nums[0];
for (int i = 1; i < n; i++) {
    f[i] = Math.min(f[i-1], nums[i]);
}

//  f[i]在arr[i:]的最大值
int[] f = new int[n+1];
f[n] = 0;
for (int i = n-1; i > 0; i--) {
    f[i] = Math.max(f[i+1], nums[i]);
}

// f[i]在arr[i:]的最小值
int[] f = new int[n+1];
f[n] = Integer.MAX_INT;
for (int i = n-1; i > 0; i --) {
    f[i] = Math.min(f[i+1], nums[i]);
}

无序数组输出第k大的值对应原数组的下标

// 获取数组长度
int n = arr.length, ans = -1;
// 将所有下标制作为 list
// boxed的作用就是将int类型的stream转成了Integer类型的Stream
var idx = Arrays.asList(IntStream.range(0, n).boxed().toArray(Integer::new));
// 将list根据原始数组值得大小进行排序
Collections.sort(idx, (i, j) -> nums[i] - nums[j]);
// 获取结果
ans = idx[k-1]