标签： medium

目标

给你一个正整数 days，表示员工可工作的总天数（从第 1 天开始）。另给你一个二维数组 meetings，长度为 n，其中 meetings[i] = [start_i, end_i] 表示第 i 次会议的开始和结束天数（包含首尾）。

返回员工可工作且没有安排会议的天数。

注意：会议时间可能会有重叠。

示例 1：

输入：days = 10, meetings = [[5,7],[1,3],[9,10]]
输出：2
解释：
第 4 天和第 8 天没有安排会议。

示例 2：

输入：days = 5, meetings = [[2,4],[1,3]]
输出：1
解释：
第 5 天没有安排会议。

示例 3：

输入：days = 6, meetings = [[1,6]]
输出：0
解释：
所有工作日都安排了会议。

说明：

• 1 <= days <= 10^9
• 1 <= meetings.length <= 10^5
• meetings[i].length == 2
• 1 <= meetings[i][0] <= meetings[i][1] <= days

思路

在区间 [1, days] 上有一些区间 [si, ei]，求没有被这些区间覆盖的正整数个数。

将区间按起点排序，记录已访问区间的最大终点 prevEnd，si - prevEnd - 1 即为当前区间与上一个区间之间的整数个数。注意特殊处理开头与结尾。

网友题解则是合并相交的区间，用总数减去区间覆盖的整数即为答案。

代码

/**
 * @date 2025-07-11 18:53
 */
public class CountDays3169 {

    public int countDays(int days, int[][] meetings) {
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
        int res = 0;
        int prevEnd = 0;
        for (int[] meeting : meetings) {
            int interval = meeting[0] - prevEnd - 1;
            res += Math.max(interval, 0);
            prevEnd = Math.max(prevEnd, meeting[1]);
        }
        return res + Math.max(0, days - prevEnd);
    }

}

性能

目标

给你一个整数 eventTime 表示一个活动的总时长，这个活动开始于 t = 0 ，结束于 t = eventTime 。

同时给你两个长度为 n 的整数数组 startTime 和 endTime 。它们表示这次活动中 n 个时间 没有重叠 的会议，其中第 i 个会议的时间为 [startTime[i], endTime[i]] 。

你可以重新安排 至多 一个会议，安排的规则是将会议时间平移，且保持原来的 会议时长 ，你的目的是移动会议后 最大化 相邻两个会议之间的 最长 连续空余时间。

请你返回重新安排会议以后，可以得到的 最大 空余时间。

注意，会议 不能 安排到整个活动的时间以外，且会议之间需要保持互不重叠。

注意：重新安排会议以后，会议之间的顺序可以发生改变。

示例 1：

输入：eventTime = 5, startTime = [1,3], endTime = [2,5]
输出：2
解释：
将 [1, 2] 的会议安排到 [2, 3] ，得到空余时间 [0, 2] 。

示例 2：

输入：eventTime = 10, startTime = [0,7,9], endTime = [1,8,10]
输出：7
解释：
将 [0, 1] 的会议安排到 [8, 9] ，得到空余时间 [0, 7] 。

示例 3：

输入：eventTime = 10, startTime = [0,3,7,9], endTime = [1,4,8,10]
输出：6
解释：
将 [3, 4] 的会议安排到 [8, 9] ，得到空余时间 [1, 7] 。

示例 4：

输入：eventTime = 5, startTime = [0,1,2,3,4], endTime = [1,2,3,4,5]
输出：0
解释：
活动中的所有时间都被会议安排满了。

说明：

• 1 <= eventTime <= 10^9
• n == startTime.length == endTime.length
• 2 <= n <= 10^5
• 0 <= startTime[i] < endTime[i] <= eventTime
• endTime[i] <= startTime[i + 1] 其中 i 在范围 [0, n - 2] 之间。

思路

有一个活动有 n 个时间不重叠的会议，重新安排 1 个会议议程，使得空余时间最大。

与 3439.重新安排会议得到最多空余时间I 相比，本题只能重新安排一个会议，但是允许打乱原有的会议顺序。

对于当前会议，如果除了其左右两侧的空余位置之外存在空余位置大于会议时间，那么空余时间是其左右两侧的空余时间加上会议时间。否则，可以将会议左移或者右移到边界，空余时间为左右空余时间之和。

因此可以求出前三大的空余时间，如果会议时间小于等于第三大的空余时间，说明总是可以移到左右空余之外。否则就需要判断当前空余时间是否大于第二、第一大的空余时间，以及是否恰好是其左右空余。

代码

/**
 * @date 2025-07-10 22:15
 */
public class MaxFreeTime3440 {

    public int maxFreeTime(int eventTime, int[] startTime, int[] endTime) {
        int n = startTime.length;
        int[] gap = new int[n + 1];
        int[] intervals = new int[n];
        Arrays.setAll(intervals, i -> endTime[i] - startTime[i]);
        int[] a = new int[]{0, 0};
        int[] b = new int[]{0, 0};
        int[] c = new int[]{0, 0};
        for (int i = 0; i <= n; i++) {
            if (i == 0) {
                gap[i] = startTime[i];
            } else if (i == n) {
                gap[i] = eventTime - endTime[i - 1];
            } else {
                gap[i] = startTime[i] - endTime[i - 1];
            }
            if (gap[i] >= a[0]) {
                c = b;
                b = a;
                a = new int[]{gap[i], i};
            } else if (gap[i] >= b[0]) {
                c = b;
                b = new int[]{gap[i], i};
            } else if (gap[i] >= c[0]) {
                c = new int[]{gap[i], i};
            }
        }
        int res = a[0];
        for (int i = 0; i < n; i++) {
            int g = gap[i] + gap[i + 1];
            if (intervals[i] > a[0]) {
                res = Math.max(res, g);
            } else if (intervals[i] <= c[0]) {
                res = Math.max(res, g + intervals[i]);
            } else if (intervals[i] <= b[0] && (b[1] != i && b[1] != i + 1)) {
                res = Math.max(res, g + intervals[i]);
            } else if (a[1] != i && a[1] != i + 1) {
                res = Math.max(res, g + intervals[i]);
            } else {
                res = Math.max(res, g);
            }
        }
        return res;
    }

}

性能

目标

给你一个整数 eventTime 表示一个活动的总时长，这个活动开始于 t = 0 ，结束于 t = eventTime 。

同时给你两个长度为 n 的整数数组 startTime 和 endTime 。它们表示这次活动中 n 个时间 没有重叠 的会议，其中第 i 个会议的时间为 [startTime[i], endTime[i]] 。

你可以重新安排 至多 k 个会议，安排的规则是将会议时间平移，且保持原来的 会议时长 ，你的目的是移动会议后 最大化 相邻两个会议之间的 最长 连续空余时间。

移动前后所有会议之间的 相对 顺序需要保持不变，而且会议时间也需要保持互不重叠。

请你返回重新安排会议以后，可以得到的 最大 空余时间。

注意，会议 不能 安排到整个活动的时间以外。

示例 1：

输入：eventTime = 5, k = 1, startTime = [1,3], endTime = [2,5]
输出：2
解释：
将 [1, 2] 的会议安排到 [2, 3] ，得到空余时间 [0, 2] 。

示例 2：

输入：eventTime = 10, k = 1, startTime = [0,2,9], endTime = [1,4,10]
输出：6
解释：
将 [2, 4] 的会议安排到 [1, 3] ，得到空余时间 [3, 9] 。

示例 3：

输入：eventTime = 5, k = 2, startTime = [0,1,2,3,4], endTime = [1,2,3,4,5]
输出：0
解释：
活动中的所有时间都被会议安排满了。

说明：

• 1 <= eventTime <= 10^9
• n == startTime.length == endTime.length
• 2 <= n <= 10^5
• 1 <= k <= n
• 0 <= startTime[i] < endTime[i] <= eventTime
• endTime[i] <= startTime[i + 1] 其中 i 在范围 [0, n - 2] 之间。

思路

有一个活动有 n 个时间不重叠的会议，重新安排 k 个会议议程，使得空余时间最大。

先根据会议时间排序，滑动窗口计算 k 个会议的总时间，以及 [end[l - 1], start[r + 1]]，相减即为窗口内的最大空余时间。

代码

/**
 * @date 2025-07-09 8:52
 */
public class MaxFreeTime3439 {

    public int maxFreeTime(int eventTime, int k, int[] startTime, int[] endTime) {
        int n = startTime.length;
        int[][] interval = new int[n + 2][2];
        interval[0][1] = 0;
        for (int i = 1; i <= n; i++) {
            interval[i] = new int[]{startTime[i - 1], endTime[i - 1]};
        }
        interval[n + 1][0] = eventTime;
        int l = 1;
        int res = 0, sum = 0;
        for (int r = 1; r <= n; r++) {
            sum += interval[r][1] - interval[r][0];
            if (r - l == k - 1) {
                res = Math.max(res, interval[r + 1][0] - interval[l - 1][1] - sum);
                sum -= interval[l][1] - interval[l][0];
                l++;
            }
        }
        return res;
    }

}

性能

目标

给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。

你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。在任意一天 d 中只能参加一场会议。

请你返回你可以参加的 最大 会议数目。

示例 1：

输入：events = [[1,2],[2,3],[3,4]]
输出：3
解释：你可以参加所有的三个会议。
安排会议的一种方案如上图。
第 1 天参加第一个会议。
第 2 天参加第二个会议。
第 3 天参加第三个会议。

示例 2：

输入：events= [[1,2],[2,3],[3,4],[1,2]]
输出：4

说明：​​​​​​

• 1 <= events.length <= 10^5
• events[i].length == 2
• 1 <= startDayi <= endDayi <= 10^5

思路

二维数组 events 表示会议的开始与结束时间，每天最多参加一次会议求最多可以参加几个会议。

按开始时间分组，记录结束时间列表，优先参加结束时间最小的会议。遍历每一天，去掉过期的会议结束时间，将当前的结束时间列表加入优先队列，取最小的结束时间，如果大于等于开始时间则计入答案。

代码

/**
 * @date 2025-07-07 9:07
 */
public class MaxEvents1353 {

    public int maxEvents(int[][] events) {
        int max = 0;
        for (int[] event : events) {
            max = Math.max(max, event[1]);
        }
        List<Integer>[] groups = new List[max + 1];
        Arrays.setAll(groups, x -> new ArrayList<>());
        for (int[] event : events) {
            groups[event[0]].add(event[1]);
        }
        PriorityQueue<Integer> q = new PriorityQueue<>();
        int res = 0;
        for (int i = 1; i <= max; i++) {
            while (!q.isEmpty() && q.peek() < i) {
                q.poll();
            }
            q.addAll(groups[i]);
            if (!q.isEmpty()) {
                res++;
                q.poll();
            }
        }
        return res;
    }

}

性能

目标

给你两个整数数组 nums1 和 nums2 ，请你实现一个支持下述两类查询的数据结构：

1. 累加 ，将一个正整数加到 nums2 中指定下标对应元素上。
2. 计数 ，统计满足 nums1[i] + nums2[j] 等于指定值的下标对 (i, j) 数目（0 <= i < nums1.length 且 0 <= j < nums2.length）。

实现 FindSumPairs 类：

• FindSumPairs(int[] nums1, int[] nums2) 使用整数数组 nums1 和 nums2 初始化 FindSumPairs 对象。
• void add(int index, int val) 将 val 加到 nums2[index] 上，即，执行 nums2[index] += val 。
• int count(int tot) 返回满足 nums1[i] + nums2[j] == tot 的下标对 (i, j) 数目。

示例：

输入：
["FindSumPairs", "count", "add", "count", "count", "add", "add", "count"]
[[[1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]], [7], [3, 2], [8], [4], [0, 1], [1, 1], [7]]
输出：
[null, 8, null, 2, 1, null, null, 11]
解释：
FindSumPairs findSumPairs = new FindSumPairs([1, 1, 2, 2, 2, 3], [1, 4, 5, 2, 5, 4]);
findSumPairs.count(7);  // 返回 8 ; 下标对 (2,2), (3,2), (4,2), (2,4), (3,4), (4,4) 满足 2 + 5 = 7 ，下标对 (5,1), (5,5) 满足 3 + 4 = 7
findSumPairs.add(3, 2); // 此时 nums2 = [1,4,5,4,5,4]
findSumPairs.count(8);  // 返回 2 ；下标对 (5,2), (5,4) 满足 3 + 5 = 8
findSumPairs.count(4);  // 返回 1 ；下标对 (5,0) 满足 3 + 1 = 4
findSumPairs.add(0, 1); // 此时 nums2 = [2,4,5,4,5,4]
findSumPairs.add(1, 1); // 此时 nums2 = [2,5,5,4,5,4]
findSumPairs.count(7);  // 返回 11 ；下标对 (2,1), (2,2), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,4) 满足 2 + 5 = 7 ，下标对 (5,3), (5,5) 满足 3 + 4 = 7

说明：

• 1 <= nums1.length <= 1000
• 1 <= nums2.length <= 10^5
• 1 <= nums1[i] <= 10^9
• 1 <= nums2[i] <= 10^5
• 0 <= index < nums2.length
• 1 <= val <= 10^5
• 1 <= tot <= 10^9
• 最多调用 add 和 count 函数各 1000 次

思路

统计元素出现次数，针对每一个 count 操作，遍历 cnt1，累加 cnt1.get(x) * cnt2.get(tot - x) 即可。

代码

/**
 * @date 2025-07-06 16:48
 */
public class FindSumPairs1865 {

    class FindSumPairs {

        int[] nums1;
        int[] nums2;
        Map<Integer, Integer> cnt1 = new HashMap<>();
        Map<Integer, Integer> cnt2 = new HashMap<>();

        public FindSumPairs(int[] nums1, int[] nums2) {
            this.nums1 = nums1;
            this.nums2 = nums2;
            for (int num : nums1) {
                cnt1.merge(num, 1, Integer::sum);
            }
            for (int num : nums2) {
                cnt2.merge(num, 1, Integer::sum);

            }
        }

        public void add(int index, int val) {
            int key = nums2[index];
            cnt2.merge(key, -1, Integer::sum);
            if (cnt2.get(key) <= 0) {
                cnt2.remove(key);
            }
            nums2[index] += val;
            cnt2.merge(key + val, 1, Integer::sum);
        }

        public int count(int tot) {
            int res = 0;
            for (Map.Entry<Integer, Integer> entry : cnt1.entrySet()) {
                int key = entry.getKey();
                int value = entry.getValue();
                res += value * cnt2.getOrDefault(tot - key, 0);
            }
            return res;
        }
    }
}

性能

目标

给你一个整数数组 nums 和一个整数 target 。

请你统计并返回 nums 中能满足其最小元素与最大元素的 和 小于或等于 target 的 非空 子序列的数目。

由于答案可能很大，请将结果对 10^9 + 7 取余后返回。

示例 1：

输入：nums = [3,5,6,7], target = 9
输出：4
解释：有 4 个子序列满足该条件。
[3] -> 最小元素 + 最大元素 <= target (3 + 3 <= 9)
[3,5] -> (3 + 5 <= 9)
[3,5,6] -> (3 + 6 <= 9)
[3,6] -> (3 + 6 <= 9)

示例 2：

输入：nums = [3,3,6,8], target = 10
输出：6
解释：有 6 个子序列满足该条件。（nums 中可以有重复数字）
[3] , [3] , [3,3], [3,6] , [3,6] , [3,3,6]

示例 3：

输入：nums = [2,3,3,4,6,7], target = 12
输出：61
解释：共有 63 个非空子序列，其中 2 个不满足条件（[6,7], [7]）
有效序列总数为（63 - 2 = 61）

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6
• 1 <= target <= 10^6

思路

统计满足条件的子序列个数，要求子序列最小元素与最大元素之和小于等于 target。

排序后考虑首位元素组成的子序列，如果满足条件，那么有 2^n-1 个，将左指针右移继续判断，如果不满足条件，右指针左移继续判断。

代码

/**
 * @date 2025-06-30 10:47
 */
public class NumSubseq1498 {

    public int numSubseq(int[] nums, int target) {
        int mod = 1000000007;
        Arrays.sort(nums);
        if (nums[0] * 2 > target) {
            return 0;
        }
        int n = nums.length;
        int l = 0;
        int r = n - 1;
        int res = 0;
        while (l <= r) {
            if (nums[l] + nums[r] <= target) {
                res = (res + pow(2, r - l, mod)) % mod;
                l++;
            } else {
                r--;
            }
        }
        return res;
    }

    public int pow(int base, int exp, int mod) {
        long res = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                res = res * base % mod;
            }
            base = (int) (((long) base * base) % mod);
            exp >>= 1;
        }
        return (int) res;
    }

}

性能

目标

给你一个二进制字符串 s 和一个正整数 k 。

请你返回 s 的 最长 子序列的长度，且该子序列对应的 二进制 数字小于等于 k 。

注意：

• 子序列可以有 前导 0 。
• 空字符串视为 0 。
• 子序列 是指从一个字符串中删除零个或者多个字符后，不改变顺序得到的剩余字符序列。

示例 1：

输入：s = "1001010", k = 5
输出：5
解释：s 中小于等于 5 的最长子序列是 "00010" ，对应的十进制数字是 2 。
注意 "00100" 和 "00101" 也是可行的最长子序列，十进制分别对应 4 和 5 。
最长子序列的长度为 5 ，所以返回 5 。

示例 2：

输入：s = "00101001", k = 1
输出：6
解释："000001" 是 s 中小于等于 1 的最长子序列，对应的十进制数字是 1 。
最长子序列的长度为 6 ，所以返回 6 。

说明：

• 1 <= s.length <= 1000
• s[i] 要么是 '0' ，要么是 '1' 。
• 1 <= k <= 10^9

思路

有一个二进制字符串 s，求满足条件的最长子序列长度，要求子序列表示的二进制数字小于等于 k。

可以计算出 k 的二进制表示 target，长度 l 最大为 30。问题的关键是能否找到长度为 l 的子序列，使得它小于等于 target，显然长度小于 l 的二进制数字必定小于等于 target。但是可以包含前导零，那么只要是 0 就可以加到左边。

贪心策略：判断长为 l 的后缀是否小于等于 k，如果是，则结果加上 l，否则加上 l - 1，然后再累加上 0 ~ n - l - 1 中 0 的个数即可。

代码

/**
 * @date 2025-06-26 8:47
 */
public class LongestSubsequence2311 {

    public int longestSubsequence(String s, int k) {
        int res = 0;
        s = "0" + s;
        int n = s.length();
        long base = 2;
        long v = s.charAt(n - 1) - '0';
        for (int i = n - 1; i > 0; i--) {
            if (v <= k) {
                res++;
                v += base * (s.charAt(i - 1) - '0');
                if (base <= k) {
                    base *= 2;
                }
            } else if (s.charAt(i) == '0') {
                res++;
            }
        }
        return res;
    }

}

性能

目标

给你一个字符串 word 和一个整数 k。

如果 |freq(word[i]) - freq(word[j])| <= k 对于字符串中所有下标 i 和 j 都成立，则认为 word 是 k 特殊字符串。

此处，freq(x) 表示字符 x 在 word 中的出现频率，而 |y| 表示 y 的绝对值。

返回使 word 成为 k 特殊字符串 需要删除的字符的最小数量。

示例 1：

输入：word = "aabcaba", k = 0
输出：3
解释：可以删除 2 个 "a" 和 1 个 "c" 使 word 成为 0 特殊字符串。word 变为 "baba"，此时 freq('a') == freq('b') == 2。

示例 2：

输入：word = "dabdcbdcdcd", k = 2
输出：2
解释：可以删除 1 个 "a" 和 1 个 "d" 使 word 成为 2 特殊字符串。word 变为 "bdcbdcdcd"，此时 freq('b') == 2，freq('c') == 3，freq('d') == 4。

示例 3：

输入：word = "aaabaaa", k = 2
输出：1
解释：可以删除 1 个 "b" 使 word 成为 2特殊字符串。因此，word 变为 "aaaaaa"，此时每个字母的频率都是 6。

说明：

• 1 <= word.length <= 10^5
• 0 <= k <= 10^5
• word 仅由小写英文字母组成。

思路

统计字符串中字符的频次，如果频次最大值减去频次最小值小于等于 k 则称为 k 特殊字符，计算使得字符串变为 k 特殊字符串最少需要删除多少个字符。

贪心策略：要删就将频次最小的字母全部删掉，关注的是最终的最大与最小频次，如果只删除部分则会使差值变大。

算法步骤如下：

1. 统计字母出现频次（去除掉频次为 0 的）并排序。
2. 从小到大枚举频次最小值 i，需要删掉的字符个数为 Σl + Σ(r - i - k)， 其中 l 表示所有小于 i 的频次，r 表示所有大于 i + k 的频次。
3. 取其最小值。

代码

/**
 * @date 2025-06-21 20:58
 */
public class MinimumDeletions3085 {

    public int minimumDeletions(String word, int k) {
        int res = Integer.MAX_VALUE;
        int[] cnt = new int[26];
        char[] chars = word.toCharArray();
        for (char c : chars) {
            cnt[c - 'a']++;
        }
        Arrays.sort(cnt);
        List<Integer> frequency = new ArrayList<>();
        for (int i : cnt) {
            if (i > 0) {
                frequency.add(i);
            }
        }
        int l = 0;
        int n = frequency.size();
        for (Integer i : frequency) {
            int deletions = l;
            l += i;
            int r = i + k;
            for (int j = n - 1; frequency.get(j) > r; j--) {
                deletions += frequency.get(j) - r;
            }
            res = Math.min(res, deletions);
        }
        return res;
    }

}

性能

目标

给你一个由字符 'N'、'S'、'E' 和 'W' 组成的字符串 s，其中 s[i] 表示在无限网格中的移动操作：

• 'N'：向北移动 1 个单位。
• 'S'：向南移动 1 个单位。
• 'E'：向东移动 1 个单位。
• 'W'：向西移动 1 个单位。

初始时，你位于原点 (0, 0)。你 最多 可以修改 k 个字符为任意四个方向之一。

请找出在 按顺序 执行所有移动操作过程中的 任意时刻 ，所能达到的离原点的 最大曼哈顿距离 。

曼哈顿距离 定义为两个坐标点 (xi, yi) 和 (xj, yj) 的横向距离绝对值与纵向距离绝对值之和，即 |xi - xj| + |yi - yj|。

示例 1：

输入：s = "NWSE", k = 1
输出：3
解释：
将 s[2] 从 'S' 改为 'N' ，字符串 s 变为 "NWNE" 。
移动操作 位置 (x, y) 曼哈顿距离 最大值
s[0] == 'N' (0, 1) 0 + 1 = 1 1
s[1] == 'W' (-1, 1) 1 + 1 = 2 2
s[2] == 'N' (-1, 2) 1 + 2 = 3 3
s[3] == 'E' (0, 2) 0 + 2 = 2 3
执行移动操作过程中，距离原点的最大曼哈顿距离是 3 。

示例 2：

输入：s = "NSWWEW", k = 3
输出：6
解释：
将 s[1] 从 'S' 改为 'N' ，将 s[4] 从 'E' 改为 'W' 。字符串 s 变为 "NNWWWW" 。
执行移动操作过程中，距离原点的最大曼哈顿距离是 6 。

说明：

• 1 <= s.length <= 10^5
• 0 <= k <= s.length
• s 仅由 'N'、'S'、'E' 和 'W' 。

思路

从原点 (0, 0) 出发，根据操作序列 s 朝四个方向移动，最多可以修改序列中 k 个方向，求能够到达的距离原点的最大曼哈顿距离。

遍历过程中记录距离变小的次数，每修改一次可以使得最大距离加 2。

网友指出每走一步可能增大的距离最多为 2 * k，但是不能超过往一个方向一直走的情况，即当前走的步数 i + 1。

代码

/**
 * @date 2025-06-20 21:47
 */
public class MaxDistance3443 {

    private static final Map<Character, int[]> MAP = new HashMap<>();

    static {
        MAP.put('N', new int[]{0, 1});
        MAP.put('S', new int[]{0, -1});
        MAP.put('E', new int[]{1, 0});
        MAP.put('W', new int[]{-1, 0});
    }

    public int maxDistance(String s, int k) {
        int res = 0;
        int d = 0;
        int prev = 0;
        int backCnt = 0;
        int[] curPos = new int[]{0, 0};
        char[] move = s.toCharArray();
        for (char dir : move) {
            prev = d;
            int[] delta = MAP.get(dir);
            int dx = delta[0];
            int dy = delta[1];
            curPos[0] += dx;
            curPos[1] += dy;
            d = Math.abs(curPos[0]) + Math.abs(curPos[1]);
            if (prev > d) {
                backCnt++;
            }
            res = Math.max(res, d + Math.min(backCnt, k) * 2);
        }
        return res;
    }
}

性能

目标

给你一个整数数组 nums 和一个整数 k 。你可以将 nums 划分成一个或多个 子序列 ，使 nums 中的每个元素都 恰好 出现在一个子序列中。

在满足每个子序列中最大值和最小值之间的差值最多为 k 的前提下，返回需要划分的 最少 子序列数目。

子序列 本质是一个序列，可以通过删除另一个序列中的某些元素（或者不删除）但不改变剩下元素的顺序得到。

示例 1：

输入：nums = [3,6,1,2,5], k = 2
输出：2
解释：
可以将 nums 划分为两个子序列 [3,1,2] 和 [6,5] 。
第一个子序列中最大值和最小值的差值是 3 - 1 = 2 。
第二个子序列中最大值和最小值的差值是 6 - 5 = 1 。
由于创建了两个子序列，返回 2 。可以证明需要划分的最少子序列数目就是 2 。

示例 2：

输入：nums = [1,2,3], k = 1
输出：2
解释：
可以将 nums 划分为两个子序列 [1,2] 和 [3] 。
第一个子序列中最大值和最小值的差值是 2 - 1 = 1 。
第二个子序列中最大值和最小值的差值是 3 - 3 = 0 。
由于创建了两个子序列，返回 2 。注意，另一种最优解法是将 nums 划分成子序列 [1] 和 [2,3] 。

示例 3：

输入：nums = [2,2,4,5], k = 0
输出：3
解释：
可以将 nums 划分为三个子序列 [2,2]、[4] 和 [5] 。
第一个子序列中最大值和最小值的差值是 2 - 2 = 0 。
第二个子序列中最大值和最小值的差值是 4 - 4 = 0 。
第三个子序列中最大值和最小值的差值是 5 - 5 = 0 。
由于创建了三个子序列，返回 3 。可以证明需要划分的最少子序列数目就是 3 。

说明：

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^5
• 0 <= k <= 10^5

思路

将数组划分为子序列，要求子序列中最大元素与最小元素的差不超过 k，并且相同的元素只能被划分到同一个子序列中，求划分的最少子序列项目。

将数组排序然后遍历，记录当前划分的最小元素，尽可能地将符合条件的元素都划分到一起，如果差值超过 k 则一定需要划分，更新最小元素。

代码

/**
 * @date 2025-06-19 9:00
 */
public class PartitionArray2294 {

    public int partitionArray(int[] nums, int k) {
        Arrays.sort(nums);
        int res = 1;
        int min = nums[0];
        for (int num : nums) {
            if (num - min <= k) {
                continue;
            }
            res++;
            min = num;
        }
        return res;
    }
}

性能