shelterofly – 第 6 页

目标

给你一个下标从 0 开始的整数数组 nums ，该数组的大小为 n ，请你计算 nums[j] - nums[i] 能求得的最大差值，其中 0 <= i < j < n 且 nums[i] < nums[j] 。

返回最大差值。如果不存在满足要求的 i 和 j ，返回 -1 。

示例 1：

输入：nums = [7,1,5,4]
输出：4
解释：
最大差值出现在 i = 1 且 j = 2 时，nums[j] - nums[i] = 5 - 1 = 4 。
注意，尽管 i = 1 且 j = 0 时 ，nums[j] - nums[i] = 7 - 1 = 6 > 4 ，但 i > j 不满足题面要求，所以 6 不是有效的答案。

示例 2：

输入：nums = [9,4,3,2]
输出：-1
解释：
不存在同时满足 i < j 和 nums[i] < nums[j] 这两个条件的 i, j 组合。

示例 3：

输入：nums = [1,5,2,10]
输出：9
解释：
最大差值出现在 i = 0 且 j = 3 时，nums[j] - nums[i] = 10 - 1 = 9 。

说明：

n == nums.length
2 <= n <= 1000
1 <= nums[i] <= 10^9

思路

找出递增元素的最大差值。

遍历数组，找出当前的最小值，用当前值减去最小值即增量元素的差值，取其最大值即可。

代码


/**
 * @date 2025-06-16 0:17
 */
public class MaximumDifference2016 {

    public int maximumDifference(int[] nums) {
        int min = Integer.MAX_VALUE;
        int res = 0;
        for (int num : nums) {
            min = Math.min(min, num);
            res = Math.max(res, num - min);
        }
        return res == 0 ? -1 : res;
    }
}

性能

目标

给你一个整数 num 。你可以对它进行以下步骤共计两次：

选择一个数字 x (0 <= x <= 9).
选择另一个数字 y (0 <= y <= 9) 。数字 y 可以等于 x 。
将 num 中所有出现 x 的数位都用 y 替换。

令两次对 num 的操作得到的结果分别为 a 和 b 。

请你返回 a 和 b 的最大差值。

注意，新的整数（a 或 b）必须不能含有前导 0，并且非 0。

示例 1：

输入：num = 555
输出：888
解释：第一次选择 x = 5 且 y = 9 ，并把得到的新数字保存在 a 中。
第二次选择 x = 5 且 y = 1 ，并把得到的新数字保存在 b 中。
现在，我们有 a = 999 和 b = 111 ，最大差值为 888

示例 2：

输入：num = 9
输出：8
解释：第一次选择 x = 9 且 y = 9 ，并把得到的新数字保存在 a 中。
第二次选择 x = 9 且 y = 1 ，并把得到的新数字保存在 b 中。
现在，我们有 a = 9 和 b = 1 ，最大差值为 8

示例 3：

输入：num = 123456
输出：820000

示例 4：

输入：num = 10000
输出：80000

示例 5：

输入：num = 9288
输出：8700

说明：

1 <= num <= 10^8

思路

从 num 中选择一个数字 d，可以将 num 中所有的 d 都替换成另一个数字（不允许包含前导零），返回能够得到的最大值与最小值的差。

与 2566.替换一个数字后的最大差值的区别是不能有前导零。

最大值：找到第一个不是 9 的位置，将 num 中所有与之相同的数字替换为 9。

最小值：找到第一个不是 1 的位置，如果是首位，将 num 中所有与之相同的数字替换为 1，否则替换为 0。

代码


/**
 * @date 2025-06-15 18:15
 */
public class MaxDiff1432 {

    public int maxDiff(int num) {
        int a = num, b = num;
        String s = String.valueOf(num);
        int n = s.length();
        int m = (int) Math.pow(10, n - 1);
        int ar = '-', br = '-';
        boolean first = false;
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (ar == '-' && c != '9') {
                ar = c;
            }
            if (br == '-' && c > '1') {
                br = c;
                first = i == 0;
            }
            if (ar == c) {
                a += (9 - (c - '0')) * m;
            }
            if (br == c) {
                b -= ((c - '0') - (first ? 1 : 0)) * m;
            }
            m /= 10;
        }
        return a - b;
    }
}

性能

目标

给你一个整数 num 。你知道 Bob 会偷偷将 0 到 9 中的一个数字替换成另一个数字。

请你返回将 num 中恰好一个数字进行替换后，得到的最大值和最小值的差为多少。

注意：

当 Bob 将一个数字 d1 替换成另一个数字 d2 时，Bob 需要将 nums 中所有 d1 都替换成 d2 。
Bob 可以将一个数字替换成它自己，也就是说 num 可以不变。
Bob 可以将数字分别替换成两个不同的数字分别得到最大值和最小值。
替换后得到的数字可以包含前导 0 。

示例 1：

输入：num = 11891
输出：99009
解释：
为了得到最大值，我们将数字 1 替换成数字 9 ，得到 99899 。
为了得到最小值，我们将数字 1 替换成数字 0 ，得到 890 。
两个数字的差值为 99009 。

示例 2：

输入：num = 90
输出：99
解释：
可以得到的最大值是 99（将 0 替换成 9），最小值是 0（将 9 替换成 0）。
所以我们得到 99 。

说明：

1 <= num <= 10^8

思路

从 num 中选择一个数字 d，可以将 num 中所有的 d 都替换成另一个数字（允许包含前导零），返回能够得到的最大值与最小值的差。

贪心策略，找到第一个不是 9 的数字 a，将 num 中所有 a 都替换为 9 得到最大数字。定义 num 第一个数字为 b，将 num 中的所有 b 替换为 0 即为最小数字。

代码


/**
 * @date 2025-06-14 9:49
 */
public class MinMaxDifference2566 {

    public int minMaxDifference(int num) {
        String s = String.valueOf(num);
        char[] chars = s.toCharArray();
        int n = s.length();
        int mul = (int) Math.pow(10, n - 1);
        int max = num, min = num;
        char maxReplace = '-';
        char minReplace = chars[0];
        for (int i = 0; i < n; i++) {
            if (maxReplace == '-' && chars[i] != '9') {
                maxReplace = chars[i];
            }
            if (minReplace == chars[i]) {
                min -= mul * (chars[i] - '0');
            }
            if (maxReplace == chars[i]) {
                max += mul * (9 - (chars[i] - '0'));
            }
            mul /= 10;
        }
        return max - min;
    }

}

性能

目标

给你一个下标从 0 开始的整数数组 nums 和一个整数 p 。请你从 nums 中找到 p 个下标对，每个下标对对应数值取差值，你需要使得这 p 个差值的最大值最小。同时，你需要确保每个下标在这 p 个下标对中最多出现一次。

对于一个下标对 i 和 j ，这一对的差值为 |nums[i] - nums[j]| ，其中 |x| 表示 x 的绝对值。

请你返回 p 个下标对对应数值最大差值的最小值。

示例 1：

输入：nums = [10,1,2,7,1,3], p = 2
输出：1
解释：第一个下标对选择 1 和 4 ，第二个下标对选择 2 和 5 。
最大差值为 max(|nums[1] - nums[4]|, |nums[2] - nums[5]|) = max(0, 1) = 1 。所以我们返回 1 。

示例 2：

输入：nums = [4,2,1,2], p = 1
输出：0
解释：选择下标 1 和 3 构成下标对。差值为 |2 - 2| = 0 ，这是最大差值的最小值。

说明：

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9
0 <= p <= (nums.length)/2

思路

取 p 个不包含相同下标的下标对，使这 p 个下标对的绝对差的最大值最小。

最小化最大值，优先考虑二分查找。问题是如何判断绝对差小于当前值的数对个数。

参考 2560.打家劫舍IV，可以使用动态规划或者贪心。

关键是贪心策略，只要相邻元素的绝对差小于二分的最大绝对差就是可选的。

代码


/**
 * @date 2025-06-13 0:09
 */
public class MinimizeMax2616 {

    public int minimizeMax(int[] nums, int p) {
        Arrays.sort(nums);
        int r = nums[nums.length - 1] - nums[0];
        int l = 0;
        int mid = l + (r - l) / 2;
        while (l <= r) {
            if (check(nums, p, mid)) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
            mid = l + (r - l) / 2;
        }
        return l;
    }

    public boolean check(int[] nums, int p, int cur) {
        int n = nums.length;
        for (int i = 1; i < n && p > 0; i++) {
            if (nums[i] - nums[i - 1] <= cur) {
                i++;
                p--;
            }
        }
        return p == 0;
    }

}

性能

目标

给你一个循环数组 nums ，请你找出相邻元素之间的最大绝对差值。

注意：一个循环数组中，第一个元素和最后一个元素是相邻的。

示例 1：

输入：nums = [1,2,4]
输出：3
解释：
由于 nums 是循环的，nums[0] 和 nums[2] 是相邻的，它们之间的绝对差值是最大值 |4 - 1| = 3 。

示例 2：

输入：nums = [-5,-10,-5]
输出：5
解释：
相邻元素 nums[0] 和 nums[1] 之间的绝对差值为最大值 |-5 - (-10)| = 5 。

说明：

2 <= nums.length <= 100
-100 <= nums[i] <= 100

思路

依题意模拟即可。

代码


/**
 * @date 2025-06-12 0:02
 */
public class MaxAdjacentDistance3423 {

    public int maxAdjacentDistance(int[] nums) {
        int res = 0;
        int n = nums.length;
        for (int i = 1; i <= n; i++) {
            res = Math.max(res, Math.abs(nums[i % n] - nums[i - 1]));
        }
        return res;
    }
}

性能

目标

给你一个字符串 s 和一个整数 k 。请你找出 s 的子字符串 subs 中两个字符的出现频次之间的最大差值，freq[a] - freq[b] ，其中：

subs 的长度至少为 k 。
字符 a 在 subs 中出现奇数次。
字符 b 在 subs 中出现偶数次。

返回最大差值。

注意，subs 可以包含超过 2 个互不相同的字符。.

子字符串是字符串中的一个连续字符序列。

示例 1：

输入：s = "12233", k = 4
输出：-1
解释：
对于子字符串 "12233" ，'1' 的出现次数是 1 ，'3' 的出现次数是 2 。差值是 1 - 2 = -1 。

示例 2：

输入：s = "1122211", k = 3
输出：1
解释：
对于子字符串 "11222" ，'2' 的出现次数是 3 ，'1' 的出现次数是 2 。差值是 3 - 2 = 1 。

示例 3：

输入：s = "110", k = 3
输出：-1

说明：

3 <= s.length <= 3 * 10^4
s 仅由数字 '0' 到 '4' 组成。
输入保证至少存在一个子字符串是由一个出现奇数次的字符和一个出现偶数次的字符组成。
1 <= k <= s.length

思路

有一个字符串 s 仅由 0 ~ 4 组成，求其长度至少为 k 的子串中，3442_奇偶频次间的最大差值I 的最大值。

// todo

代码

性能

目标

给你一个由小写英文字母组成的字符串 s 。

请你找出字符串中两个字符 a1 和 a2 的出现频次之间的最大差值 diff = a1 - a2，这两个字符需要满足：

a1 在字符串中出现奇数次。
a2 在字符串中出现偶数次。

返回最大差值。

示例 1：

输入：s = "aaaaabbc"
输出：3
解释：
字符 'a' 出现 奇数次 ，次数为 5 ；字符 'b' 出现 偶数次 ，次数为 2 。
最大差值为 5 - 2 = 3 。

示例 2：

输入：s = "abcabcab"
输出：1
解释：
字符 'a' 出现 奇数次 ，次数为 3 ；字符 'c' 出现 偶数次 ，次数为 2 。
最大差值为 3 - 2 = 1 。

说明：

3 <= s.length <= 100
s 仅由小写英文字母组成。
s 至少由一个出现奇数次的字符和一个出现偶数次的字符组成。

思路

统计字符串中字符的出现频次，计算奇数频次最大值与偶数频次最小值的差。

代码


/**
 * @date 2025-06-10 8:42
 */
public class MaxDifference3442 {

    public int maxDifference(String s) {
        int[] cnt = new int[26];
        char[] chars = s.toCharArray();
        for (char c : chars) {
            cnt[c - 'a']++;
        }
        int oddMax = 0;
        int evenMin = Integer.MAX_VALUE;
        for (int i : cnt) {
            if (i == 0) {
                continue;
            }
            if (i % 2 == 1) {
                oddMax = Math.max(i, oddMax);
            } else {
                evenMin = Math.min(i, evenMin);
            }
        }
        return oddMax - evenMin;
    }
}

性能

目标

给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。

示例 1:

输入: n = 13, k = 2
输出: 10
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

示例 2:

输入: n = 1, k = 1
输出: 1

说明:

1 <= k <= n <= 10^9

思路

求 1 ~ n 的所有数字按字典序排列后的第 k 个数字。

本来想要参考 386.字典序排数取第 k 个数字。但是数据范围太大，O(n) 的解法不可行。

题目标签显示的是字典树。想象一棵 10 叉树，根为 0，从第一个孩子 1 开始，如果其子树大小小于剩余的数字个数，直接跳过，访问兄弟节点 2，否则进入下一层，从第一个孩子 10 开始，计算其子树大小，如果小于剩余数字个数，访问兄弟节点 11，否则进入下一层。以此类推。

如何统计子树的大小？可以将当前根节点 l 与兄弟节点 r 一起向下计算，当前层的节点个数 = Math.min(r, n + 1) - 1 - l + 1 即 Math.min(r, n + 1) - l。比如，l == 100, r == 200，计算 100 ~ 200 - 1 的数字个数。注意 r 与 n + 1 取最小值，因为要减 1 所以比较的是 n + 1。

代码


/**
 * @date 2025-06-09 8:44
 */
public class FindKthNumber440 {

    public int findKthNumber(int n, int k) {
        int i = 1;
        k--;
        while (k > 0) {
            int cnt = subTreeNodesCnt(i, n);
            if (cnt <= k) {
                k -= cnt;
                i++;
            } else {
                k--;
                i *= 10;
            }
        }

        return i;
    }

    public int subTreeNodesCnt(int root, int n) {
        int cnt = 0;
        long l = root;
        long r = root + 1;
        while (l <= n) {
            cnt += Math.min(r, n + 1) - l;
            l *= 10;
            r *= 10;
        }
        return cnt;
    }
}

性能

386.字典序排数

目标

给你一个整数 n ，按字典序返回范围 [1, n] 内所有整数。

你必须设计一个时间复杂度为 O(n) 且使用 O(1) 额外空间的算法。

示例 1：

输入：n = 13
输出：[1,10,11,12,13,2,3,4,5,6,7,8,9]

示例 2：

输入：n = 2
输出：[1,2]

说明：

1 <= n <= 5 * 10^4

思路

将 1 ~ n 的所有整数按照字典序排序，要求时间复杂度为 O(n)，空间复杂度为 O(1)。

想象遍历一颗字典树，优先扩展（乘以 10），如果超过 n，则优先将个位数加一（遍历兄弟节点），如果需要进位，则返回父节点（除以10）并将个位数加一（父节点的兄弟节点），接着执行同样的逻辑，扩展，个位数加一，回退。

代码


/**
 * @date 2025-06-08 18:15
 */
public class LexicalOrder386 {

    public List<Integer> lexicalOrder(int n) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0, j = 1; i < n; i++) {
            res.add(j);
            if (j * 10 <= n) {
                j *= 10;
            } else {
                while (j % 10 == 9 || j >= n) {
                    j /= 10;
                }
                j++;
            }
        }
        return res;
    }

}

性能

3170.删除星号以后字典序最小的字符串

目标

给你一个字符串 s 。它可能包含任意数量的 '' 字符。你的任务是删除所有的 '' 字符。

当字符串还存在至少一个 '*' 字符时，你可以执行以下操作：

删除最左边的 '*' 字符，同时删除该星号字符左边一个字典序最小的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。

请你返回删除所有 '*' 字符以后，剩余字符连接而成的字典序最小的字符串。

示例 1：

输入：s = "aaba*"
输出："aab"
解释：
删除 '*' 号和它左边的其中一个 'a' 字符。如果我们选择删除 s[3] ，s 字典序最小。

示例 2：

输入：s = "abc"
输出："abc"
解释：
字符串中没有 '*' 字符。

说明：

1 <= s.length <= 10^5
s 只含有小写英文字母和 '*' 字符。
输入保证操作可以删除所有的 '*' 字符。

思路

有一个包含任意数量 * 的字符串，每次操作可以删掉 * 以及它左侧的一个字典序最小的字符，如果有多个可以，删除任意一个。求删除所有 * 之后能够得到的字典序最小的字符串。

贪心算法，优先删除左侧字典序最小且下标最大的字符即可。

代码


/**
 * @date 2025-06-07 9:37
 */
public class ClearStars3170 {

    public String clearStars(String s) {
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> {
            int compare = a[0] - b[0];
            if (compare != 0) {
                return compare;
            }
            return b[1] - a[1];
        });
        char[] chars = s.toCharArray();
        int n = chars.length;
        for (int i = 0; i < n; i++) {
            char c = chars[i];
            if (c != '*') {
                q.offer(new int[]{c, i});
            } else {
                q.poll();
            }
        }
        char[] res = new char[q.size()];
        PriorityQueue<int[]> tmp = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        tmp.addAll(q);
        int i = 0;
        while (!tmp.isEmpty()) {
            int[] c = tmp.poll();
            res[i++] = (char) c[0];
        }
        return new String(res);
    }
}

2025 年 8 月
一	二	三	四	五	六	日
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31