目录
一、有效括号（LeetCode 20・简单）
题目描述
解题思路
Java 代码实现（标准栈版）
复杂度分析
核心知识点总结
二、寻找两个正序数组的中位数（LeetCode 4・困难）
题目描述
解题思路
核心思想
Java 代码实现（标准二分版）
复杂度分析
核心知识点总结
三、算法思想对比与学习路径
学习建议
四、总结
大家好，今天我们来拆解两道经典算法题：一道是栈的入门必刷题有效括号，另一道是二分查找的天花板难题寻找两个正序数组的中位数。前者帮你彻底吃透栈的核心思想，后者带你解锁二分查找的高阶应用，非常适合作为算法学习的进阶内容～
一、有效括号（LeetCode 20・简单）
题目描述
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s，判断字符串是否有效。
有效字符串需满足：
示例：
plaintext
输入：s = "()[]{}"
输出：true
输入：s = "(]"
输出：false
解题思路
这道题是 ** 栈（Stack）** 的经典入门应用，核心逻辑非常简单：
- 遇到左括号 (、{、[，就把对应的右括号压入栈中（方便后续匹配）
- 遇到右括号，判断栈是否为空（空则说明没有对应左括号，直接返回 false），并弹出栈顶元素，判断是否与当前右括号匹配
Java 代码实现（标准栈版）
java
运行
import java.util.Stack;
public class ValidParentheses {
public boolean isValid(String s) {
// 奇数长度一定无效
if (s.length() % 2 != 0) {
return false;
}
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
// 遇到左括号，压入对应的右括号
if (c == '(') {
stack.push(')');
} else if (c == '{') {
stack.push('}');
} else if (c == '[') {
stack.push(']');
} else {
// 遇到右括号，判断栈是否为空，或栈顶不匹配
if (stack.isEmpty() || stack.pop() != c) {
return false;
}
}
}
// 栈为空说明所有括号都正确闭合
return stack.isEmpty();
}
}
复杂度分析
- 时间复杂度：O(n)，只遍历一次字符串，每个字符入栈 / 出栈最多一次。
- 空间复杂度：O(n)，最坏情况（全是左括号）需要存储整个字符串长度的栈空间。
核心知识点总结
二、寻找两个正序数组的中位数（LeetCode 4・困难）
题目描述
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
算法的时间复杂度应该为 O(log(m+n))。
示例：
plaintext
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
解题思路
这道题的核心难点是时间复杂度要求 O(log(m+n))，因此不能用简单的合并数组法（时间复杂度 O(m+n)），必须用二分查找的思路。
核心思想
中位数的本质是：将两个数组的所有元素分成左右两部分，左部分元素个数 = 右部分元素个数（或差 1），且左部分最大值 ≤ 右部分最小值。
我们的目标就是找到这个「分割线」：
- leftMax1：nums1 左部分的最大值（i == 0 时为 -∞）
- rightMin1：nums1 右部分的最小值（i == m 时为 +∞）
- leftMax2：nums2 左部分的最大值（j == 0 时为 -∞）
- rightMin2：nums2 右部分的最小值（j == n 时为 +∞）
- 总长度为奇数：中位数 = max(leftMax1, leftMax2)
- 总长度为偶数：中位数 = (max(leftMax1, leftMax2) + min(rightMin1, rightMin2)) / 2
- 若 leftMax1 > rightMin2：说明 nums1 分割点太靠右，需要左移（right = i – 1）
- 若 leftMax2 > rightMin1：说明 nums1 分割点太靠左，需要右移（left = i + 1）
Java 代码实现（标准二分版）
java
运行
public class FindMedianSortedArrays {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// 保证nums1是长度更短的数组，简化二分
if (nums1.length > nums2.length) {
int[] temp = nums1;
nums1 = nums2;
nums2 = temp;
}
int m = nums1.length;
int n = nums2.length;
int left = 0;
int right = m;
// 左部分总元素个数 = (m + n + 1) / 2，保证奇数时左部分多1个
int totalLeft = (m + n + 1) / 2;
while (left <= right) {
// nums1的分割点
int i = left + (right – left) / 2;
// nums2的分割点
int j = totalLeft – i;
// 边界处理：分割点在数组两端时，用无穷大/无穷小代替
int leftMax1 = i == 0 ? Integer.MIN_VALUE : nums1[i – 1];
int rightMin1 = i == m ? Integer.MAX_VALUE : nums1[i];
int leftMax2 = j == 0 ? Integer.MIN_VALUE : nums2[j – 1];
int rightMin2 = j == n ? Integer.MAX_VALUE : nums2[j];
// 找到正确的分割线
if (leftMax1 <= rightMin2 && leftMax2 <= rightMin1) {
// 总长度为奇数
if ((m + n) % 2 == 1) {
return Math.max(leftMax1, leftMax2);
} else {
// 总长度为偶数
return (Math.max(leftMax1, leftMax2) + Math.min(rightMin1, rightMin2)) / 2.0;
}
} else if (leftMax1 > rightMin2) {
// nums1分割点太靠右，左移
right = i – 1;
} else {
// nums1分割点太靠左，右移
left = i + 1;
}
}
// 理论上不会走到这里
return 0.0;
}
}
复杂度分析
- 时间复杂度：O(logmin(m,n))，只对长度更短的数组进行二分，满足题目要求的 O(log(m+n))。
- 空间复杂度：O(1)，仅使用常数级额外空间。
核心知识点总结
三、算法思想对比与学习路径
表格
| 栈（Stack） | 后进先出（LIFO） | 括号匹配、逆序、DFS、表达式求值 | O(n) |
| 二分查找 | 分治，每次缩小一半范围 | 有序数组查找、中位数计算 | O(logn) |
学习建议
四、总结
- 有效括号：栈的经典入门题，核心是利用栈的后进先出特性匹配括号，是学习栈的必刷题。
- 寻找两个正序数组的中位数：二分查找的天花板难题，核心是通过二分查找找到分割线，将两个数组分成左右两部分，从而计算中位数，是算法面试的高频难题。
