【教3妹学编程-算法题】交换得到字典序最小的数组

插： 前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。
坚持不懈，越努力越幸运，大家一起学习鸭~~~

3妹：2哥2哥， 你有没有看到新闻：周海媚姐因病医治无效，于2023年12月11日离开了我们。
2哥 : 看到了，真是个悲伤的消息，早晨还看到辟谣，以为没事了呢。
3妹：是啊，#再见周芷若#
2哥：童年的女神，周海媚演的这版“周芷若”真的很深入人心！被评为“最美周芷若”
3妹：哎，人有生老病死，R.I.P.
2哥：唉，说点高兴的话题吧。3妹，如果拿你一样东西，换取你10年寿命，你愿意拿什么来换。
3妹：活着多好啊， 拿什么我也不换。 等等，也可以拿我的2哥来换，哈哈。
2哥：切，我还不同意呢。
3妹：说到交换，我看到一个交换的题目，让我也来考考你吧~

题目：

给你一个下标从 0 开始的 正整数 数组 nums 和一个 正整数 limit 。

在一次操作中，你可以选择任意两个下标 i 和 j，如果 满足 |nums[i] - nums[j]| <= limit ，则交换 nums[i] 和 nums[j] 。

返回执行任意次操作后能得到的 字典序最小的数组 。

如果在数组 a 和数组 b 第一个不同的位置上，数组 a 中的对应元素比数组 b 中的对应元素的字典序更小，则认为数组 a 就比数组 b 字典序更小。例如，数组 [2,10,3] 比数组 [10,2,3] 字典序更小，下标 0 处是两个数组第一个不同的位置，且 2 < 10 。

示例 1：

输入：nums = [1,5,3,9,8], limit = 2
输出：[1,3,5,8,9]
解释：执行 2 次操作：

• 交换 nums[1] 和 nums[2] 。数组变为 [1,3,5,9,8] 。
• 交换 nums[3] 和 nums[4] 。数组变为 [1,3,5,8,9] 。
  即便执行更多次操作，也无法得到字典序更小的数组。
  注意，执行不同的操作也可能会得到相同的结果。
  示例 2：

输入：nums = [1,7,6,18,2,1], limit = 3
输出：[1,6,7,18,1,2]
解释：执行 3 次操作：

• 交换 nums[1] 和 nums[2] 。数组变为 [1,6,7,18,2,1] 。
• 交换 nums[0] 和 nums[4] 。数组变为 [2,6,7,18,1,1] 。
• 交换 nums[0] 和 nums[5] 。数组变为 [1,6,7,18,1,2] 。
  即便执行更多次操作，也无法得到字典序更小的数组。
  示例 3：

输入：nums = [1,7,28,19,10], limit = 3
输出：[1,7,28,19,10]
解释：[1,7,28,19,10] 是字典序最小的数组，因为不管怎么选择下标都无法执行操作。

提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
1 <= limit <= 10^9

思路：

排序，
把 nums[i]及其下标 i 绑在一起排序（也可以单独排序下标），然后把 nums分成若干段，每一段都是递增的且相邻元素之差不超过 limit，那么这一段可以随意排序。

java代码：

class Solution {
    public int[] lexicographicallySmallestArray(int[] nums, int limit) {
        int n = nums.length;
        Integer[] ids = new Integer[n];
        for (int i = 0; i < n; i++) {
            ids[i] = i;
        }
        Arrays.sort(ids, (i, j) -> nums[i] - nums[j]);

        int[] ans = new int[n];
        for (int i = 0; i < n; ) {
            int st = i;
            for (i++; i < n && nums[ids[i]] - nums[ids[i - 1]] <= limit; i++) ;
            Integer[] subIds = Arrays.copyOfRange(ids, st, i);
            Arrays.sort(subIds);
            for (int j = 0; j < subIds.length; j++) {
                ans[subIds[j]] = nums[ids[st + j]];
            }
        }
        return ans;
    }
}