思路
一个prefix数组 一个 suffix 数组
在idx = i处可以使用prefix 和 suffix的一些性质，比如乘积，或者在i上左边的最小值，右边的最小值
本质是为了快速的在当前i上能够利用信息避免重复计算
题目
初见使用在了leetcode 368 周赛 Q2:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public int minimumSum(int[] nums) {
int n = nums.length;
int[] leftMin = new int[n];
int[] rightMin = new int[n];
leftMin[0] = Integer.MAX_VALUE;
for (int i = 1; i < n; i++) {
leftMin[i] = Math.min(leftMin[i - 1], nums[i - 1]);
}
rightMin[n - 1] = Integer.MAX_VALUE;
for (int i = n - 2; i >= 0; i--) {
rightMin[i] = Math.min(rightMin[i + 1], nums[i + 1]);
}
int minSum = Integer.MAX_VALUE;
for (int i = 1; i < n - 1; i++) {
if (nums[i] > leftMin[i] && nums[i] > rightMin[i]) {
minSum = Math.min(minSum, nums[i] + leftMin[i] + rightMin[i]);
}
}
return minSum == Integer.MAX_VALUE ? -1 : minSum;
}
}
|
