目录
一，3105. 最长的严格递增或递减子数组
二，3106. 满足距离约束且字典序最小的字符串
三，3107. 使数组中位数等于 K 的最少操作数
四，3108. 带权图里旅途的最小代价
一，3105. 最长的严格递增或递减子数组
本题求最长递增/递减的子数组长度（严格递增/递减 即不能相等），可以先遍历数组求出最长递增子数组，再遍历一边求出最长递减子数组，返回两者的最大值，代码如下：
class Solution {
public int longestMonotonicSubarray(int[] nums) {
int ans = 1;
int n = nums.length;
boolean flg = false;
for(int l=0,r=1; r<n; r++){
if(nums[r]-nums[r-1]>0){//递增
ans = Math.max(ans, r-l+1);
continue;
}else{
l = r;
}
}
for(int l=0,r=1; r<n; r++){
if(nums[r]-nums[r-1]<0){//递减
ans = Math.max(ans, r-l+1);
continue;
}else{
l = r;
}
}
return ans;
}
}还有一种一次循环遍历就能解决的算法，就是分组循环算法，可以发现上述的两个循环其实只是 if 语句中的判断条件不同，其他没变，而这个 if 语句中判断条件就是来判断当前子数组是递增/递减的，所以当只使用一个循环的时候，就需要多一个变量来判断当前的子数组是递增/递减的，代码如下：
class Solution {
public int longestMonotonicSubarray(int[] nums) {
int n = nums.length;
int i = 1;
int ans = 1;
while(i < n){
if(nums[i] == nums[i-1]){//严格递增/递减
i++;
continue;
}
int i0 = i-1;//记录左端点
boolean flg = nums[i] > nums[i-1];//判断以i0为左端点的子数组是递增/递减
while(i<n && nums[i]!=nums[i-1] && flg == (nums[i] > nums[i-1])){
//保证是递增或递减
ans = Math.max(ans, i-i0+1);
i++;
}
}
return ans;
}
}二，3106. 满足距离约束且字典序最小的字符串
本题题意：给定一个字符串 s，可以任意修改其中的字符 k 次（对字符进行+1-1操作），返回一个字典序最小的字符串，（注：只有小写英文字母，z 和 a 首尾相连）
要返回一个字典序最小的字符串，就是优先将靠前的字符变成 a，如果不够就将当前字符变成ch - k，后面的字符不变。
这里需要注意的点是：这里的26个字母是一个类似于循环数组的东西，可以将该字符减小 ch-'a' 次变成a，也可以将该字符增加 'z' - ch + 1 次，使其先变成 z 再变成 a，所以要优先考虑操作次数小的方式。
代码如下：
class Solution {
public String getSmallestString(String s, int k) {
StringBuilder res = new StringBuilder();
for(char ch : s.toCharArray()){
int cnt1 = ch - 'a';//直接变成a
int cnt2 = 'z' - ch + 1;//从z到a
int mn = Math.min(cnt1, cnt2);
if(k >= mn){//剩下的操作次数可以将ch变成'a'
k -= mn;
res.append('a');
}else{//剩下的操作次数不能把ch变成'a'
res.append((char)(ch-k));
k = 0;
}
}
return res.toString();
}
}三，3107. 使数组中位数等于 K 的最少操作数
本题就是一道找中位数的题，可以先把数组排个序，当数组长度 n 为奇数时，中位数恰好是下标为 n/2 的数，而当数组长度为偶数时，因题目要求较大的数是中位数，这时的中位数恰好也是下标为 n/2 的数。
可以直接根据中位数和 k 的大小来分类讨论：
- 如果 nums[n/2] > k，说明 n/2 之后的都数大于 k 不会影响中位数的产生，只需要往前遍历，如果 nums[i] > k，nums[i]要变成 k，需要操作nums[i]-k次，如果 nums[i] <= k，就说明 i 及之前的数都小于 k，不会影响中位数的产生，直接break
- 如果nums[n/2] <= k，说明 n/2 之前的数都小于等于 k 不会影响中位数的产生，只需要往后遍历，如果 nums[i] > k，nums[i]要变成 k，需要操作k-nums[i]次，如果 nums[i] >= k，就说明 i 及之后的数都小于 k，不会影响中位数的产生，直接break
class Solution {
public long minOperationsToMakeMedianK(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int m = n/2;
long ans = 0;
if(nums[m] > k){
for(int i=m; i>=0; i--){//只要考虑前半部分
if(nums[i]<k)
break;
ans += nums[i] - k;
}
}else{
for(int i=m; i<n; i++){//只要考虑后半部分
if(nums[i]>k)
break;
ans += k - nums[i];
}
}
return ans;
}
}四，3108. 带权图里旅途的最小代价
本题要求 &的最小值，由&的性质可知，&的数越多，&的结果就越小，所以求 s -> t 的最小值，就是求 s，t 所在连通块的所有权值的 & 值。
一共分成三种情况：
- s，t 不在同一个联通块中，即他们不相连，返回 -1
- s，t 是同一个点，返回 0
- s，t 在同一连通块中，返回该连通块所有边的权值的 &值
需要一个数组ids，ids[i] 表示 i 点属于 ids[i] 这个连通块，需要一个链表listAnd，listAnd.get(i) 表示第 i 个连通块的 and值，接下来就是计算了。
代码如下：
class Solution {
List<Integer> listAnd = new ArrayList<>();//统计连通块的and值
public int[] minimumCost(int n, int[][] edges, int[][] query) {
//建图
List<int[]>[] g = new ArrayList[n];
Arrays.setAll(g, e->new ArrayList<>());
for(int[] e : edges){
int x = e[0], y = e[1], w = e[2];
g[x].add(new int[]{y, w});
g[y].add(new int[]{x, w});
}
int[] ids = new int[n];//统计每个点在哪个连通块中，同时用作记忆化
Arrays.fill(ids, -1);//如果ids[i]>=0表示i已经访问过
for(int i=0; i<n; i++){
if(ids[i] < 0){
//计算每个连通块的and值
listAnd.add(dfs(i, g, ids));
}
}
int[] ans = new int[query.length];
for(int i=0; i<query.length; i++){
int w = query[i][0];
int v = query[i][1];
if(w == v){
ans[i] = 0;
}else if(ids[w] != ids[v]){
ans[i] = -1;
}else{
ans[i] = listAnd.get(ids[w]);
}
}
return ans;
}
//计算每个联通块的and值
int dfs(int x, List<int[]>[] g, int[] ids){
int res = -1;
ids[x] = listAnd.size();
for(int[] y : g[x]){
res &= y[1];
if(ids[y[0]] < 0){
res &= dfs(y[0], g, ids);
}
}
return res;
}
}
