【LeetCode题解】670. 最大交换+2765. 最长交替子数组+2865. 美丽塔 I

本文主要是介绍【LeetCode题解】670. 最大交换+2765. 最长交替子数组+2865. 美丽塔 I，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

670. 最大交换

思路：

从后往前遍历整数的字符数组，找到第一个比当前最大值小的数字，然后将该数字与最大值进行交换。

1. 将给定的整数转换为字符数组。
2. 初始化变量 maxIdx 为字符数组的最后一个索引，用于记录当前最大值的索引。
3. 初始化变量 idx1 和 idx2 为-1，用于记录需要交换的两个索引。
4. 从字符数组的最后一个元素开始往前遍历。
   • 如果当前字符比最大值大，则更新最大值的索引 maxIdx。
   • 如果当前字符比最大值小，则将当前索引赋值给 idx1，将 maxIdx 赋值给 idx2。
5. 判断是否存在需要交换的索引：
   • 如果 idx1大于等于0，说明存在需要交换的索引。调用 swap 函数交换字符数组中 idx1 和 idx2 位置对应的字符。将字符数组转换为整数，并返回结果。
   • 如果不存在需要交换的索引，直接返回原始整数。

public int maximumSwap(int num) {char[] charArray = String.valueOf(num).toCharArray(); // 将整数转换为字符数组int n = charArray.length;int maxIdx = n - 1; // 记录当前最大值的索引，默认为最后一位int idx1 = -1, idx2 = -1; // 记录需要交换的两个索引，默认为-1for (int i = n - 1; i >= 0; i--) { // 从后往前遍历字符数组if (charArray[i] > charArray[maxIdx]) { // 如果当前字符比最大值大maxIdx = i; // 更新最大值的索引} else if (charArray[i] < charArray[maxIdx]) { // 如果当前字符比最大值小idx1 = i; // 记录第一个需要交换的索引idx2 = maxIdx; // 记录第二个需要交换的索引为当前最大值的索引}}if (idx1 >= 0) { // 如果存在需要交换的索引swap(charArray, idx1, idx2); // 交换两个索引对应的字符return Integer.parseInt(new String(charArray)); // 将字符数组转换为整数并返回} else {return num; // 如果不存在需要交换的索引，则返回原始整数}
}public void swap(char[] charArray, int i, int j) { // 交换字符数组中两个索引对应的字符char temp = charArray[i];charArray[i] = charArray[j];charArray[j] = temp;
}

2765. 最长交替子数组

思路：

计算给定数组中的最大交替子数组的长度。交替子数组是指相邻元素差值符号交替的子数组。代码通过两层循环遍历数组，以每个元素为起点，判断其与后续元素的差值是否交替，并记录最长的交替子数组长度。最后返回最大交替子数组的长度

1. 初始化左右边界指针 left 和 right，分别指向数组的第一个元素和最后一个元素。
2. 当左右指针未重合时，循环执行以下步骤：
   • 计算中间值索引 mid，即 (left + right) / 2。
   • 如果中间值等于目标值，则直接返回中间值索引 mid。
   • 如果中间值大于目标值，则将右边界指针 right 更新为 mid - 1。
   • 如果中间值小于目标值，则将左边界指针 left 更新为 mid + 1。
3. 如果未找到目标值，则返回 -1。

public int alternatingSubarray(int[] nums) {int ans = -1, n = nums.length;  // 初始化结果 ans 为 -1，获取数组长度 nfor (int i = 0; i < n; ++i) {  // 遍历数组，以每个元素为起点int k = 1;  // 设置差值的初始值为 1int j = i;  // 定义指针 j，从当前位置开始for (; j + 1 < n && nums[j + 1] - nums[j] == k; ++j) {  // 在满足条件的情况下，不断向后移动指针 jk *= -1;  // 每次循环更新差值的符号（正负交替）}if (j - i + 1 > 1) {  // 判断当前子数组长度是否大于 1ans = Math.max(ans, j - i + 1);  // 更新结果 ans，取较大的子数组长度}}return ans;  // 返回最大交替子数组的长度
}

2865. 美丽塔 I

public long maximumSumOfHeights(List<Integer> maxHeights) {long ans = 0;int n = maxHeights.size();// 遍历每一个位置for (int i = 0; i < n; ++i) {int y = maxHeights.get(i);long t = y;// 向左遍历，计算左边最小高度的和for (int j = i - 1; j >= 0; --j) {y = Math.min(y, maxHeights.get(j));t += y;}// 重置y为当前位置的高度y = maxHeights.get(i);// 向右遍历，计算右边最小高度的和for (int j = i + 1; j < n; ++j) {y = Math.min(y, maxHeights.get(j));t += y;}// 更新最大和ans = Math.max(ans, t);}return ans;
}

这篇关于【LeetCode题解】670. 最大交换+2765. 最长交替子数组+2865. 美丽塔 I的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！