目录
一，3411. 最长乘积等价子数组
本题数据范围小，直接暴力枚举，代码如下：
class Solution {
public int maxLength(int[] nums) {
int n = nums.length;
int ans = 0;
for(int l=0; l<n; l++){
for(int r=l; r<n; r++){
int p = 1, g = 0, lc = 1;
for(int i=l; i<=r; i++){
p *= nums[i];
g = gcd(nums[i], g);
lc = lcm(nums[i], lc);
}
if(p == g * lc) ans = Math.max(ans, r-l+1);
}
}
return ans;
}
int gcd(int a, int b){
return b==0?a:gcd(b,a%b);
}
int lcm(int a, int b){
return a*b/gcd(a,b);
}
}二，3412. 计算字符串的镜像分数
本题就是要存储26个字母的出现的所有下标，对于 s[i] 来说，需要找到相应镜像的字母 c，然后返回字母 c 最近的下标，也就是说，需要一个先进后出的数据结构——栈来存储 26 个字母的下标，代码如下：
class Solution {
public long calculateScore(String s) {
Stack<Integer>[] st = new Stack[26];
Arrays.setAll(st, e->new Stack<>());
long ans = 0;
for(int i=0; i<s.length(); i++){
int c = s.charAt(i) - 'a';
if(!st[25-c].isEmpty()){
ans += i - st[25-c].pop();
}else{
st[c].push(i);
}
}
return ans;
}
}三，3413. 收集连续 K 个袋子可以获得的最多硬币数量
本题求连续 k 个袋子可获得的最多硬币数量，就是维护一个长度为 k 的滑动窗口，关键的问题就变成了如何维护窗口的更新（进/出），求最多，贪心的想对于一个区间 [L，R]，需要尽可能多的包含这个区间，那么有两种情况——以 L 为左端点，向右维护一个长为 k 的窗口；以 R 为右端点，向左维护一个长为 k 的窗口。需要分别求出上述两种情况，取最大值。
这里写以 L 为左端点，向右维护一个长为 k 的窗口的维护方法，另一种可以通过镜像的方式，复用此代码。如图所示：
代码如下：
class Solution {
long window(int[][] f, int k){
int n = f.length;
long ans = 0;
long cover = 0, uncover = 0;
for(int i=0, j=0; i<n; i++){
long l = f[i][0], r = f[i][1], c = f[i][2];
cover += (r - l + 1) * c;
while(f[j][1] < r - k + 1){
cover -= (long)(f[j][1] - f[j][0] + 1) * f[j][2];
j++;
}
uncover = Math.max((long)(r - k + 1 - f[j][0]) * f[j][2], 0) ;
ans = Math.max(ans, cover - uncover);
}
return ans;
}
public long maximumCoins(int[][] coins, int k) {
Arrays.sort(coins, (x, y) -> x[0] - y[0]);
long ans = window(coins, k);
for(int[] c : coins){
int t = -c[0];
c[0] = -c[1];
c[1] = t;
}
int n = coins.length;
for(int i=0; i<n/2; i++){
int[] t = coins[i];
coins[i] = coins[n-1-i];
coins[n-1-i] = t;
}
return Math.max(ans, window(coins, k));
}
}四，3414. 不重叠区间的最大得分
定义f[i][j]: 在前 i 个区间选出 j 个不重叠区间的最大得分和此时字典序最小的区间下标顺序。标准的0-1背包做法，难点在于维护字典序最小的区间下标顺序。
代码如下：
class Solution {
private record Tuple(long w, List<Integer> id){}
private record Info(int l, int r, int w, int i){}
public int[] maximumWeight(List<List<Integer>> intervals) {
int n = intervals.size();
Info[] t = new Info[n];
for(int i=0; i<n; i++){
List<Integer> x = intervals.get(i);
int l = x.get(0), r = x.get(1), w = x.get(2);
t[i] = new Info(l, r, w, i);
}
Arrays.sort(t, (x, y) -> x.r - y.r);
Tuple[][] f = new Tuple[n+1][5];
Arrays.setAll(f[0], e->new Tuple(0, new ArrayList<>()));
for(int i=0; i<n; i++){
int l = t[i].l, r = t[i].r, w = t[i].w;
int k = search(t, l-1, i);
f[i+1][0] = new Tuple(0, new ArrayList<>());
for(int j=1; j<5; j++){
long s1 = f[i][j].w;
long s2 = f[k+1][j-1].w + w;
if(s1 > s2){
f[i+1][j] = f[i][j];
continue;
}
List<Integer> tmp = new ArrayList<>(f[k+1][j-1].id);
tmp.add(t[i].i);
Collections.sort(tmp);
if(s1 == s2 && compareLists(tmp, f[i][j].id) > 0){
tmp = f[i][j].id;
}
f[i+1][j] = new Tuple(s2, tmp);
}
}
return f[n][4].id.stream().mapToInt(v->v).toArray();
}
int compareLists(List<Integer> a, List<Integer> b){
for(int i=0; i<Math.min(a.size(), b.size()); i++){
if(!a.get(i).equals(b.get(i)))
return a.get(i) - b.get(i);
}
return a.size() - b.size();
}
int search(Info[] t, int k, int r){
int l = 0;
while(l <= r){
int mid = (l + r) >>> 1;
if(t[mid].r <= k){
l = mid + 1;
}else{
r = mid - 1;
}
}
return l - 1;
}
}