算法刷题记录——LeetCode篇(3.10) [第291~300题](持续更新)

更新时间：2025-04-02

• 算法题解目录汇总：算法刷题记录——题解目录汇总
• 技术博客总目录：计算机技术系列博客——目录页

优先整理热门100及面试150，不定期持续更新，欢迎关注！

---

295. 数据流的中位数

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
例如 arr = [2,3,4] 的中位数是 3 。
例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。

实现 MedianFinder 类:

MedianFinder();
// 初始化 MedianFinder 对象。
void addNum(int num);
// 将数据流中的整数 num 添加到数据结构中。
double findMedian();
// 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1：

输入:
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]

输出:
[null, null, null, 1.5, null, 2.0]

解释：

MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

提示：

• -10^5 <= num <= 10^5
• 在调用 findMedian 之前，数据结构中至少有一个元素
• 最多 5 * 10^4 次调用 addNum 和 findMedian

---

方法：双堆法

使用两个堆（大顶堆和小顶堆）分别存储数据流的较小和较大半部分，实现中位数的快速查询。

1. 数据结构设计：

   • 大顶堆存储较小半部分元素，堆顶为最大元素
   • 小顶堆存储较大半部分元素，堆顶为最小元素
   • 始终维持大顶堆元素数 ≥ 小顶堆元素数

2. 添加元素流程：

   1. 新元素先加入大顶堆
   2. 将大顶堆的最大值传递给小顶堆
   3. 若小顶堆元素更多，返还最小值到大顶堆

3. 中位数计算：

   • 当元素总数为奇数时，直接返回大顶堆堆顶
   • 当元素总数为偶数时，返回两堆顶平均值

代码实现(Java)：

class MedianFinder {private PriorityQueue<Integer> maxHeap; // 存储较小的一半（大顶堆）private PriorityQueue<Integer> minHeap; // 存储较大的一半（小顶堆）public MedianFinder() {maxHeap = new PriorityQueue<>(Collections.reverseOrder());minHeap = new PriorityQueue<>();}public void addNum(int num) {// 1. 先加入大顶堆并传递最大值到小顶堆maxHeap.offer(num);minHeap.offer(maxHeap.poll());// 2. 平衡堆大小，保证大顶堆不小于小顶堆if (minHeap.size() > maxHeap.size()) {maxHeap.offer(minHeap.poll());}}public double findMedian() {// 根据堆大小差异返回中位数return maxHeap.size() > minHeap.size() ? maxHeap.peek() : (maxHeap.peek() + minHeap.peek()) / 2.0;}
}

复杂度分析

• 时间复杂度：
  • addNum(): O(log n) 堆插入和删除操作
  • findMedian(): O(1) 直接访问堆顶
• 空间复杂度：O(n) 存储所有元素

---

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4

解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

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

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

• 1 <= nums.length <= 2500
• -10^4 <= nums[i] <= 10^4

进阶：
你能将算法的时间复杂度降低到 O(n log(n)) 吗?

方法一：动态规划

使用动态规划数组 dp[i] 表示以 nums[i] 结尾的最长递增子序列长度。对于每个元素，遍历其之前的所有元素，若当前元素更大，则更新 dp[i]。

代码实现(Java)：

class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];Arrays.fill(dp, 1);int max = 1;for (int i = 1; i < nums.length; i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}max = Math.max(max, dp[i]);}return max;}
}

方法二：贪心 + 二分查找

维护一个 tails 数组，tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素。通过二分查找快速定位插入或替换位置。

代码实现(Java)：

class Solution {public int lengthOfLIS(int[] nums) {List<Integer> tails = new ArrayList<>();for (int num : nums) {int left = 0, right = tails.size();// 二分查找第一个 >= num 的位置while (left < right) {int mid = left + (right - left) / 2;if (tails.get(mid) < num) {left = mid + 1;} else {right = mid;}}if (left == tails.size()) {tails.add(num);} else {tails.set(left, num);}}return tails.size();}
}

复杂度分析

方法	时间复杂度	空间复杂度	适用场景
动态规划	O(n²)	O(n)	简单直观，小规模数据
二分+贪心	O(n log n)	O(n)	大规模数据，效率要求高

---

---

声明

1. 本文版权归 CSDN 用户 Allen Wurlitzer 所有，遵循CC-BY-SA协议发布，转载请注明出处。
2. 本文题目来源 力扣-LeetCode ，著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。