4.Heap／Priority Queue题目：

Leetcode 973. K Closest Points

题目描述

给定平面上的 n 个点和一个整数 k，找到平面上距离原点最近的 k 个点。结果可以按任意顺序返回。

点的坐标的范围是 $[-10000,10000][-10000,\; 10000]$。

例如，当 $k=3k\; =\; 3$，且平面上有如下的五个点时，距离原点最近的三个点是 $[-2,2]\mathrm{、}[1,3][-2,2]、[1,3]$ 和 $[3,-2][3,\; -2]$。

(-2,2)
(1,3)
(3,-2)
(2,2)
(-1,1)

解法

本题可以使用最大堆来解决。先将所有点的坐标和距离原点的距离计算出来，然后将这些点加入到最大堆中。当堆的大小超过 $kk$ 时，就将堆顶元素弹出。最后堆中剩余的元素就是距离原点最近的 $kk$ 个点。

代码

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (b[0] * b[0] + b[1] * b[1]) - (a[0] * a[0] + a[1] * a[1]));
        for (int[] point : points) {
            pq.offer(point);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        int[][] res = new int[k][2];
        int i = 0;
        while (!pq.isEmpty()) {
            res[i++] = pq.poll();
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：$O(nlogk)O(nlogk)$，其中 $nn$ 是点的数量。需要遍历所有点，并且每个点都需要加入到堆中，时间复杂度为 $O(nlogk)O(nlogk)$。
• 空间复杂度：$O(k)O(k)$，需要使用一个大小为 $kk$ 的堆来存储最近的 $kk$ 个点。

Leetcode 347. Top k Largest Elements

题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1：

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2：

输入: nums = [1], k = 1
输出: [1]

提示：

• 1 <= nums.length <= 105
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证 nums 中的所有元素都在范围 [1, 104] 内  

解法

本题的解法是使用哈希表统计每个数字出现的次数，然后使用小根堆（优先队列）维护前 k 个高频元素。具体步骤如下：

1. 使用哈希表统计每个数字出现的次数。
2. 创建一个小根堆，遍历哈希表中的每个数字，将其加入到小根堆中。
3. 当小根堆的大小超过 k 时，弹出堆顶元素。
4. 最终小根堆中剩余的元素就是出现频率前 k 高的元素。

代码

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(map::get));
        for (int num : map.keySet()) {
            heap.offer(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        int[] res = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            res[i] = heap.poll();
        }
        return res;
    }
}

复杂度分析

时间复杂度：$O(nlogk)O(nlogk)$，其中 $nn$ 是数组的长度。遍历哈希表的时间复杂度是 $O(n)O(n)$，每次插入和删除元素的时间复杂度是 $O(logk)O(logk)$，所以总时间复杂度是 $O(nlogk)O(nlogk)$。

空间复杂度：$O(n)O(n)$，其中 $nn$ 是数组的长度。需要使用哈希表和小根堆各自存储 $nn$ 个元素的信息。

Leetcode 23. Merge K Sorted Lists

题目描述

给你一个链表数组，每个链表都已经按升序排列。 请你将所有链表合并到一个升序链表中，返回合并后的链表。   示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

解法

本题可以使用分治法来解决。将链表数组分成两个子数组，对每个子数组递归调用函数，返回合并后的两个链表。最后将两个合并后的链表再合并成一个链表。

具体实现时，可以使用归并排序的思想。将链表数组分成两个子数组，对每个子数组递归调用函数，返回合并后的两个链表。最后将两个合并后的链表再合并成一个链表。

代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) {
            return null;
        }
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int left, int right) {
        if (left == right) {
            return lists[left];
        }
        int mid = left + (right - left) / 2;
        ListNode l1 = merge(lists, left, mid);
        ListNode l2 = merge(lists, mid + 1, right);
        return mergeTwoLists(l1, l2);
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

复杂度分析

时间复杂度：$O(nlogk)O(nlogk)$，其中 $kk$ 是链表数组的长度，$nn$ 是所有链表的节点数的总和。分治的时间复杂度是 $O(logk)O(logk)$，每次合并两个链表的时间复杂度是 $O(n)O(n)$，最终的时间复杂度是 $O(nlogk)O(nlogk)$。

空间复杂度：$O(logk)O(logk)$，其中 $kk$ 是链表数组的长度。递归调用的栈空间的深度是 $O(logk)O(logk)$，最坏情况下会有 $kk$ 个函数调用，因此空间复杂度是 $O(logk)O(logk)$。

Leetcode 264. Ugly Number II

题目描述

编写一个程序，找出第 n 个丑数。

丑数就是质因数只包含 2, 3, 5 的正整数。

示例:

输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

• 1 是丑数。
• n 不超过1690。

解法

本题的解法是使用动态规划。我们定义 $dp[i]dp[i]$ 表示第 $ii$ 个丑数。初始时，$dp[1]=1dp[1]\; =\; 1$。

接下来，我们需要找到下一个丑数。我们可以从之前的丑数中选择一个丑数 $dp[j]dp[j]$，使得 $dp[j]\times 2dp[j]\backslash times2$、$dp[k]\times 3dp[k]\backslash times3$、$dp[l]\times 5dp[l]\backslash times5$ 中的最小值大于 $dp[i-1]dp[i-1]$，即：

$\min (dp[j]\times 2,dp[k]\times 3,dp[l]\times 5)>dp[i-1]\backslash min(dp[j]\backslash times2,\; dp[k]\backslash times3,\; dp[l]\backslash times5)\; >\; dp[i-1]$

然后我们就可以得到下一个丑数 $dp[i]dp[i]$：

$dp[i]=\min (dp[j]\times 2,dp[k]\times 3,dp[l]\times 5)dp[i]\; =\; \backslash min(dp[j]\backslash times2,\; dp[k]\backslash times3,\; dp[l]\backslash times5)$

在选择丑数 $dp[j]dp[j]$、$dp[k]dp[k]$、$dp[l]dp[l]$ 时，我们需要保证它们的乘积不小于 $dp[i-1]dp[i-1]$，并且如果有多个丑数满足要求，我们需要选择最小的丑数。

最终，$dp[n]dp[n]$ 就是第 $nn$ 个丑数。

代码

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int i = 1, j = 1, k = 1;
        for (int m = 2; m <= n; m++) {
            int x = dp[i] * 2, y = dp[j] * 3, z = dp[k] * 5;
            int min = Math.min(x, Math.min(y, z));
            if (min == x) {
                i++;
            }
            if (min == y) {
                j++;
            }
            if (min == z) {
                k++;
            }
            dp[m] = min;
        }
        return dp[n];
    }
}

复杂度分析

时间复杂度：$O(n)O(n)$，其中 $nn$ 是要求的丑数的个数。

空间复杂度：$O(n)O(n)$，需要使用额外的空间存储所有丑数。

Leetcode 1086. High Five

题目描述

给定一个没有重复数字的列表，nums，返回每个数字在列表中的前5个高的元素的平均值，以降序返回。

示例 1：

输入：nums = [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]] 输出：[[1,87.4],[2,88.6]] 解释： 1 学生的平均分是 87.4 ，第二学生的平均分是 88.6 。所以第一个学生的高分为 [91,92,60,65,87]，而第二个学生的高分为 [93,97,77,100,76]。因此返回 [[1,87.4],[2,88.6]]。

提示：

• 1 <= nums.length <= 1000
• 1 <= nums[i][0] <= 10^6
• 0 <= nums[i][1] <= 100
• 题目数据保证每个学生都有至少 5 个成绩。

解法

本题的解法是使用哈希表，将每个学生的成绩存储在哈希表中，然后对于每个学生，按照成绩从高到低排序，取前5个成绩的平均值即可。

代码

class Solution {
    public int[][] highFive(int[][] items) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] item : items) {
            int id = item[0];
            int score = item[1];
            if (!map.containsKey(id)) {
                map.put(id, new ArrayList<>());
            }
            map.get(id).add(score);
        }
        int[][] res = new int[map.size()][2];
        int i = 0;
        for (int id : map.keySet()) {
            List<Integer> scores = map.get(id);
            Collections.sort(scores, Collections.reverseOrder());
            int sum = 0;
            for (int j = 0; j < 5; j++) {
                sum += scores.get(j);
            }
            res[i][0] = id;
            res[i][1] = sum / 5;
            i++;
        }
        Arrays.sort(res, (a, b) -> a[0] - b[0]);
        return res;
    }
}

复杂度分析

时间复杂度：$O(nlogn)O(nlogn)$，其中 $nn$ 是数组的长度。对于每个学生，需要对其成绩进行排序，时间复杂度是 $O(logn)O(logn)$。因此总时间复杂度是 $O(nlogn)O(nlogn)$。

空间复杂度：$O(n)O(n)$，其中 $nn$ 是数组的长度。需要使用哈希表存储每个学生的成绩。

Leetcode 88. Merge Sorted Arrays

题目描述

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

提示：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[i] <= 109

解法

本题可以使用双指针法解决。定义两个指针分别指向 nums1 和 nums2 的末尾，比较两个指针指向的元素大小，将较大的元素放到 nums1 的末尾。然后将指针指向较大元素的数组向前移动一位，直到其中一个数组的元素全部放入 nums1 中。

需要注意的是，当 nums2 的元素全部放入 nums1 中后，如果 nums1 中还有剩余的元素，不需要进行任何操作，因为这些元素已经是有序的。

代码

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1, p2 = n - 1;
        int p = m + n - 1;
        while (p1 >= 0 && p2 >= 0) {
            if (nums1[p1] > nums2[p2]) {
                nums1[p] = nums1[p1];
                p1--;
            } else {
                nums1[p] = nums2[p2];
                p2--;
            }
            p--;
        }
        System.arraycopy(nums2, 0, nums1, 0, p2 + 1);
    }
}

复杂度分析

时间复杂度：$O(m+n)O(m+n)$，其中 $mm$ 和 $nn$ 分别是 nums1 和 nums2 的长度。双指针遍历一遍数组，时间复杂度为 $O(m+n)O(m+n)$。

空间复杂度：$O(1)O(1)$。只需要常数级别的额外空间。

Leetcode 692. Top K Frequent Words

题目描述

给一非空的单词列表，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

示例 1：

输入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]
解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。
    注意，按字母顺序 "i" 在 "love" 之前。

示例 2：

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词，
    出现次数依次为 4, 3, 2 和 1 次。

注意：

• 假定 k 总为有效值， 1 ≤ k ≤ 集合元素数。
• 输入的单词均由小写字母组成。

解法

本题的解法主要是使用哈希表记录每个单词出现的次数，然后将哈希表中的元素放入一个优先队列中，根据出现次数进行排序。如果出现次数相同，按照字母顺序进行排序。

代码

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
            (a, b) -> (a.getValue() == b.getValue() ? b.getKey().compareTo(a.getKey()) : a.getValue() - b.getValue())
        );
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            pq.offer(entry);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        List<String> res = new ArrayList<>();
        while (!pq.isEmpty()) {
            res.add(0, pq.poll().getKey());
        }
        return res;
    }
}

复杂度分析

时间复杂度：$O(nlogk)O(nlogk)$，其中 $nn$ 是单词列表的长度。遍历单词列表的时间复杂度是 $O(n)O(n)$，将元素放入优先队列中的时间复杂度是 $O(logk)O(logk)$，最坏情况下需要将所有元素都放入优先队列中，因此总时间复杂度是 $O(nlogk)O(nlogk)$。

空间复杂度：$O(n)O(n)$，其中 $nn$ 是单词列表的长度。需要使用哈希表存储每个单词出现的次数，以及优先队列存储出现次数最大的 $kk$ 个单词。

Leetcode 378. Kth Smallest Element in a Sorted Matrix

题目描述

给你一个 n x n 矩阵 matrix 和一个整数 k ，矩阵中的每一行和每一列都按非递减顺序排序，你需要从这个矩阵中找到第 k 小的元素。

你需要返回这个元素。

示例 1：

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小的元素是 13

示例 2：

输入：matrix = [[-5]], k = 1
输出：-5

提示：

• n == matrix.length
• n == matrix[i].length
• 1 <= n <= 300
• $-10^9-10^9$ <= matrix[i][j] <= $10^{9}10^9$
• 题目数据保证 matrix 中的所有行和列都按非递减顺序排序
• 1 <= k <= n^2

解法

这道题可以使用最小堆来解决。首先将矩阵中的第一列元素加入堆中，然后每次弹出堆顶元素，将其所在行的下一个元素加入堆中。这样做的原因是矩阵的每一行和每一列都是按非递减顺序排序的，因此每一行中当前最小的元素一定是该行的第一个元素，而当前最小的元素可能在堆顶，也可能在堆中的其他位置。

代码

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        for (int i = 0; i < n; i++) {
            minHeap.offer(new int[]{matrix[i][0], i, 0});
        }
        for (int i = 0; i < k - 1; i++) {
            int[] curr = minHeap.poll();
            if (curr[2] != n - 1) {
                minHeap.offer(new int[]{matrix[curr[1]][curr[2] + 1], curr[1], curr[2] + 1});
            }
        }
        return minHeap.poll()[0];
    }
}

复杂度分析

时间复杂度：$O(klogn)O(klogn)$，其中 $nn$ 是矩阵的大小。初始化最小堆需要 $O(nlogn)O(nlogn)$ 的时间，每次弹出堆顶元素并加入一个新元素需要 $O(logn)O(logn)$ 的时间，总共需要弹出 $k-1k-1$ 个元素，因此时间复杂度是 $O(klogn)O(klogn)$。

空间复杂度：$O(n)O(n)$，其中 $nn$ 是矩阵的大小。最小堆需要 $O(n)O(n)$ 的空间。

Leetcode 295. Find Median from Data Stream （标准解法是双heap，但是SortedDict会非常容易）

题目描述

中位数是有序列表中间的数。如果列表长度是偶数，中间两个数的平均值就是中位数。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。

示例：

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

进阶:

如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？ 如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？

解法

首先我们需要明确中位数的定义，中位数是有序列表中间的数。那么我们可以使用两个优先队列（堆）来维护数据流中的数，一个小根堆用来存储比中位数大的数，一个大根堆用来存储比中位数小的数。同时我们要保证两个堆的大小相差不超过 1，这样才能保证中位数的正确性。

每次插入一个数时，我们先将这个数插入小根堆，然后将小根堆的堆顶元素（即最小值）取出并插入大根堆中。如果此时大根堆的大小比小根堆的大小大 1，我们就将大根堆的堆顶元素取出并插入小根堆中。这样就可以保证两个堆的大小相差不超过 1。

当我们需要求中位数时，如果两个堆的大小相等，说明数据流中有偶数个数，中位数就是两个堆的堆顶元素的平均值。否则，中位数就是大根堆的堆顶元素。

优化：

如果数据流中所有整数都在 0 到 100 范围内，我们可以使用桶排序来维护数据流中的数，这样可以大大提高效率。如果数据流中 99% 的整数都在 0 到 100 范围内，我们可以使用两个桶来维护数据流中的数，一个桶用来存储比中位数大的数，一个桶用来存储比中位数小的数。同时我们要保证两个桶的大小相差不超过 1，这样才能保证中位数的正确性。

代码

class MedianFinder {
    PriorityQueue<Integer> small; // 小根堆
    PriorityQueue<Integer> large; // 大根堆

    /** initialize your data structure here. */
    public MedianFinder() {
        small = new PriorityQueue<>();
        large = new PriorityQueue<>((a, b) -> (b - a));
    }
    
    public void addNum(int num) {
        small.offer(num);
        large.offer(small.poll());
        if (large.size() > small.size()) {
            small.offer(large.poll());
        }
    }
    
    public double findMedian() {
        if (small.size() == large.size()) {
            return (small.peek() + large.peek()) / 2.0;
        } else {
            return small.peek();
        }
    }
}

复杂度分析

时间复杂度：

• addNum：$O(logn)O(logn)$，其中 $nn$ 是数据流中的元素个数。插入元素的时间复杂度是 $O(logn)O(logn)$，因为需要将元素插入到堆中。
• findMedian：$O(1)O(1)$，取中位数的时间复杂度是 $O(1)O(1)$，因为可以直接返回堆顶元素。

空间复杂度：$O(n)O(n)$，其中 $nn$ 是数据流中的元素个数。需要使用两个堆存储数据流中的元素。

Leetcode 767. Reorganize String

题目描述

给定一个字符串 S，检查是否能重新排布其中的字母，使得两相邻的字符不同。

若可行，输出任意可行的结果。若不可行，返回空字符串。

示例 1:

输入: S = "aab" 输出: "aba"

示例 2:

输入: S = "aaab" 输出: ""

注意:

S 只包含小写字母并且长度在[1, 500]区间内。

解法

本题的解法是贪心算法。首先统计每个字母出现的次数，然后将出现次数最多的字母放在偶数位，其余字母按顺序放在奇数位。

为了保证出现次数最多的字母不会相邻，我们可以将两个偶数位之间插入一个奇数位，然后将出现次数最多的字母放在这个奇数位上。

最后，如果有任何一个字母的出现次数超过了 $(n+1)\mathrm{/}2(n+1)/2$，那么无法重新排布，返回空字符串。

代码

class Solution {
    public String reorganizeString(String S) {
        int[] count = new int[26];
        int maxCount = 0;
        int n = S.length();
        for (int i = 0; i < n; i++) {
            char c = S.charAt(i);
            count[c-'a']++;
            maxCount = Math.max(maxCount, count[c-'a']);
        }
        if (maxCount > (n+1)/2) {
            return "";
        }
        char[] res = new char[n];
        int even = 0, odd = 1;
        for (int i = 0; i < 26; i++) {
            char c = (char) (i + 'a');
            while (count[i] > 0 && odd < n) {
                res[odd] = c;
                count[i]--;
                odd += 2;
            }
            while (count[i] > 0) {
                res[even] = c;
                count[i]--;
                even += 2;
            }
        }
        return new String(res);
    }
}

复杂度分析

时间复杂度：$O(n)O(n)$，其中 $nn$ 是字符串的长度。需要遍历字符串一次，统计每个字母出现的次数，然后遍历一次 $2626$ 个字母，将字母按照规则放入结果数组中。

空间复杂度：$O(26)O(26)$，即 $O(1)O(1)$。需要使用一个长度为 $2626$ 的数组统计每个字母出现的次数，以及一个长度为 $nn$ 的字符数组存储结果。

Leetcode 1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (这个题用单调双端队列、TreeMap、双heap都可以)

题目描述

给定一个整数数组 nums 和一个整数 limit，请你找出该数组中所有满足其最大值与最小值的差小于等于 limit 的 非空 连续子数组，并返回其中 最长 的一个。

示例 1：

输入：nums = [8,2,4,7], limit = 4
输出：2
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4. 
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4. 
因此，满足题意的最长子数组的长度为 2 。

示例 2：

输入：nums = [10,1,2,4,7,2], limit = 5
输出：4
解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。

示例 3：

输入：nums = [4,2,2,2,4,4,2,2], limit = 0
输出：3

提示：

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

解法

使用单调队列来维护每个子数组的最大值和最小值，以及它们的下标。每次向右移动窗口时，将窗口右端点加1，并将右端点对应的元素加入到单调队列中。如果队列中的最大值和最小值之差大于 limit，则需要将队列中最左边的元素弹出，直到队列中的最大值和最小值之差小于等于 limit。每次移动窗口时，都需要更新最长的满足条件的子数组的长度。

时间复杂度：$O(n)O(n)$，其中 $nn$ 是数组的长度。因为每个元素最多只会被加入和弹出队列一次。

空间复杂度：$O(n)O(n)$，其中 $nn$ 是数组的长度。需要使用一个队列来维护单调队列。

代码

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        int len = nums.length;
        Deque<Integer> maxQ = new ArrayDeque<>(); // 单调递减队列，存储最大值
        Deque<Integer> minQ = new ArrayDeque<>(); // 单调递增队列，存储最小值
        int left = 0, right = 0;
        int ans = 0;
        while (right < len) {
            while (!maxQ.isEmpty() && nums[right] > nums[maxQ.peekLast()]) {
                maxQ.pollLast();
            }
            while (!minQ.isEmpty() && nums[right] < nums[minQ.peekLast()]) {
                minQ.pollLast();
            }
            maxQ.offerLast(right);
            minQ.offerLast(right);
            while (!maxQ.isEmpty() && !minQ.isEmpty() && nums[maxQ.peekFirst()] - nums[minQ.peekFirst()] > limit) {
                if (maxQ.peekFirst() < minQ.peekFirst()) {
                    left = maxQ.pollFirst() + 1;
                } else {
                    left = minQ.pollFirst() + 1;
                }
            }
            ans = Math.max(ans, right - left + 1);
            right++;
        }
        return ans;
    }
}

复杂度分析

时间复杂度：$O(n)O(n)$，其中 $nn$ 是数组的长度。因为每个元素最多只会被加入和弹出队列一次。

空间复杂度：$O(n)O(n)$，其中 $nn$ 是数组的长度。需要使用一个队列来维护单调队列。

Leetcode 895. Maximum Frequency Stack

题目描述

实现 FreqStack，模拟类似栈的数据结构的操作的一个类。

FreqStack 有两个函数：

• push(int x)，将整数 x 推入栈中。
• pop()，它移除并返回栈中出现最频繁的元素。
  • 如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。

示例：

["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
输出：[null,null,null,null,null,null,null,5,7,5,4]
解释：
执行六次 .push 操作后，栈自底向上为 [5,7,5,7,4,5]。然后：

pop() -> 返回 5，因为 5 是出现频率最高的。栈变成 [5,7,5,7,4]。
pop() -> 返回 7，因为 5 和 7 都是频率最高的，但 7 最接近栈顶。栈变成 [5,7,5,4]。
pop() -> 返回 5 。栈变成 [5,7,4]。
pop() -> 返回 4 。栈变成 [5,7]。

提示：

- 对 FreqStack.push(int x) 的调用中 0 <= x <= 10^9。
- 如果栈的元素数目为零，则保证不会调用 FreqStack.pop()。
- 单个测试样例中，对 FreqStack.push 的总调用次数不会超过 10000。
- 单个测试样例中，对 FreqStack.pop 的总调用次数不会超过 10000。
- 所有测试样例中，对 FreqStack.push 和 FreqStack.pop 的总调用次数不会超过 150000。

解法

使用两个 Map 来实现，第一个 Map 用来保存每个元素的出现次数，第二个 Map 用来保存每个出现次数对应的元素列表。然后在 pop 的时候，找到出现次数最大的元素，如果有多个，取出最近的那个。

代码

class FreqStack {
    private Map<Integer, Integer> freqMap;
    private Map<Integer, Stack<Integer>> groupMap;
    private int maxFreq;

    public FreqStack() {
        freqMap = new HashMap<>();
        groupMap = new HashMap<>();
        maxFreq = 0;
    }

    public void push(int x) {
        int freq = freqMap.getOrDefault(x, 0) + 1;
        freqMap.put(x, freq);
        maxFreq = Math.max(maxFreq, freq);
        groupMap.computeIfAbsent(freq, k -> new Stack<>()).push(x);
    }

    public int pop() {
        Stack<Integer> group = groupMap.get(maxFreq);
        int x = group.pop();
        freqMap.put(x, freqMap.get(x) - 1);
        if (group.isEmpty()) {
            maxFreq--;
        }
        return x;
    }
}

复杂度分析

• 时间复杂度：push 操作的时间复杂度为 O(1)，pop 操作的时间复杂度为 O(1)。
• 空间复杂度：需要使用两个 Map 存储元素出现次数和元素列表，空间复杂度为 O(n)。