目录

一，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';//直接变成aint cnt2 = 'z' - ch + 1;//从z到aint 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;}
}