标签： todo

目标

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

如果子数组中所有元素都相等，则认为子数组是一个 等值子数组 。注意，空数组是 等值子数组 。

从 nums 中删除最多 k 个元素后，返回可能的最长等值子数组的长度。

子数组 是数组中一个连续且可能为空的元素序列。

示例 1：

输入：nums = [1,3,2,3,1,3], k = 3
输出：3
解释：最优的方案是删除下标 2 和下标 4 的元素。
删除后，nums 等于 [1, 3, 3, 3] 。
最长等值子数组从 i = 1 开始到 j = 3 结束，长度等于 3 。
可以证明无法创建更长的等值子数组。

示例 2：

输入：nums = [1,1,2,2,1,1], k = 2
输出：4
解释：最优的方案是删除下标 2 和下标 3 的元素。 
删除后，nums 等于 [1, 1, 1, 1] 。 
数组自身就是等值子数组，长度等于 4 。 
可以证明无法创建更长的等值子数组。

说明：

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

思路

给定一个数组 nums 和一个正整数k，最多可以删除数组中k个元素，问数组中最长的等值子数组有多长，所谓等值子数组就是数组中的值完全相同。

直接的想法是记录每个相同元素的下标index，然后计算它们之间的距离 gap，使用滑动窗口来计算最多可以消除的 gap 数量。

注意不能优先消除序列中距离小的 gap，也就是说只能按照顺序去消除，否则可能会截断等值子数组。

刚开始使用哈希表记录相同元素的下标序列，结果提示超出内存限制，后来改用数组解决了问题。

Map在不断添加元素时可能需要进行扩容，每次扩容都需要重新分配更大的内存空间。 但我直接指定初始大小还是超出限制。

原来用了两个哈希表，indexMap 与 gapMap，后来 indexMap 改成了 List[]，gapMap 则直接在循环中计算并添加到 ArrayList 中。

注意这不是一个固定大小的窗口，如果按照固定大小的窗口去实现还是会超时。

代码

/**
 * @date 2024-05-23 0:11
 */
public class LongestEqualSubarray2831 {

    public int longestEqualSubarray_v1(List<Integer> nums, int k) {
        if (nums.size() == 0) {
            return 0;
        }
        int res = 0;
        List<Integer>[] indexMap = new List[100001];
        for (int i = 0; i < nums.size(); i++) {
            int val = nums.get(i);
            if (indexMap[val] == null) {
                indexMap[val] = new ArrayList<>();
            }
            indexMap[val].add(i);
        }
        for (List<Integer> index : indexMap) {
            if (index == null) {
                continue;
            }
            int i = 0;
            ArrayList<Integer> gaps = new ArrayList<>();
            for (int j = 1; j < index.size(); j++) {
                gaps.add(index.get(j) - index.get(i++) - 1);
            }
            int cnt = k;
            int gapNums = 0;
            int left = 0;
            int right = 0;
            while (right < gaps.size()) {
                while (cnt >= 0 && right < gaps.size()) {
                    cnt -= gaps.get(right);
                    if (cnt >= 0) {
                        right++;
                    }
                }
                gapNums = Math.max(gapNums, right - left);
                while (left < gaps.size() && cnt < 0) {
                    cnt += gaps.get(left);
                    left++;
                }
                right++;
            }

            res = Math.max(res, gapNums + 1);
        }
        return res;
    }
}

性能

又是勉强通过。//todo 性能分析与优化

目标

矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线，沿右下方向一直到矩阵末尾的元素。例如，矩阵 mat 有 6 行 3 列，从 mat[2][0] 开始的 矩阵对角线 将会经过 mat[2][0]、mat[3][1] 和 mat[4][2] 。

给你一个 m * n 的整数矩阵 mat ，请你将同一条 矩阵对角线 上的元素按升序排序后，返回排好序的矩阵。

说明：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 100
• 1 <= mat[i][j] <= 100

思路

排序是一大块内容，有机会统一总结一下。// todo

这里偷懒使用了优先队列，先放到队列里面排序，然后再写回去。

代码

/**
 * @date 2024-04-29 0:26
 */
public class DiagonalSort1329 {

    public int[][] diagonalSort(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int i;
        int j;
        PriorityQueue<Integer> q = new PriorityQueue();
        for (int col = 0; col < n; col++) {
            j = col;
            i = 0;
            while (i < m && j < n) {
                q.offer(mat[i++][j++]);
            }
            j = col;
            i = 0;
            while (i < m && j < n) {
                mat[i++][j++] = q.poll();
            }
        }
        for (int row = 1; row < m; row++) {
            j = 0;
            i = row;
            while (i < m && j < n) {
                q.offer(mat[i++][j++]);
            }
            j = 0;
            i = row;
            while (i < m && j < n) {
                mat[i++][j++] = q.poll();
            }
        }

        return mat;
    }

}

性能

这个题涉及到hash表与二分查找，发现之前2529.正整数和负整数的最大计数里面寻找上界写错了。

有时间了再整理一下吧。