目录一、有效括号LeetCode 20・简单题目描述解题思路Java 代码实现标准栈版复杂度分析核心知识点总结二、寻找两个正序数组的中位数LeetCode 4・困难题目描述解题思路核心思想Java 代码实现标准二分版复杂度分析核心知识点总结三、算法思想对比与学习路径学习建议四、总结大家好今天我们来拆解两道经典算法题一道是栈的入门必刷题有效括号另一道是二分查找的天花板难题寻找两个正序数组的中位数。前者帮你彻底吃透栈的核心思想后者带你解锁二分查找的高阶应用非常适合作为算法学习的进阶内容一、有效括号LeetCode 20・简单题目描述给定一个只包括(){}[]的字符串s判断字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。示例plaintext输入s ()[]{} 输出true 输入s (] 输出false解题思路这道题是 ** 栈Stack** 的经典入门应用核心逻辑非常简单栈的特性后进先出LIFO完美匹配括号「先开后闭」的顺序。遍历字符串遇到左括号(、{、[就把对应的右括号压入栈中方便后续匹配遇到右括号判断栈是否为空空则说明没有对应左括号直接返回 false并弹出栈顶元素判断是否与当前右括号匹配最终校验遍历结束后栈必须为空说明所有左括号都被正确闭合否则返回 falseJava 代码实现标准栈版java运行import java.util.Stack; public class ValidParentheses { public boolean isValid(String s) { // 奇数长度一定无效 if (s.length() % 2 ! 0) { return false; } StackCharacter 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)最坏情况全是左括号需要存储整个字符串长度的栈空间。核心知识点总结栈的核心应用场景匹配问题、逆序问题、深度优先搜索DFS、表达式求值等。括号匹配的关键左括号入栈、右括号匹配出栈最终栈空才有效。优化技巧先判断字符串长度是否为奇数直接排除无效情况提升效率。二、寻找两个正序数组的中位数LeetCode 4・困难题目描述给定两个大小分别为m和n的正序从小到大数组nums1和nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为 O(log(mn))。示例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(mn))因此不能用简单的合并数组法时间复杂度 O(mn)必须用二分查找的思路。核心思想中位数的本质是将两个数组的所有元素分成左右两部分左部分元素个数 右部分元素个数或差 1且左部分最大值 ≤ 右部分最小值。我们的目标就是找到这个「分割线」为了简化计算我们始终让nums1是长度更短的数组m ≤ n保证二分查找的效率。对nums1进行二分找到分割点i则nums2的分割点j (m n 1) / 2 - i保证左部分总元素个数 右部分总元素个数。定义四个边界值leftMax1nums1左部分的最大值i 0时为-∞rightMin1nums1右部分的最小值i m时为∞leftMax2nums2左部分的最大值j 0时为-∞rightMin2nums2右部分的最小值j n时为∞当满足leftMax1 ≤ rightMin2且leftMax2 ≤ rightMin1时分割线正确计算中位数总长度为奇数中位数 max(leftMax1, leftMax2)总长度为偶数中位数 (max(leftMax1, leftMax2) min(rightMin1, rightMin2)) / 2若不满足条件调整二分边界若leftMax1 rightMin2说明nums1分割点太靠右需要左移right i - 1若leftMax2 rightMin1说明nums1分割点太靠左需要右移left i 1Java 代码实现标准二分版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(mn))。空间复杂度O(1)仅使用常数级额外空间。核心知识点总结二分查找的高阶应用不直接查找元素而是查找「分割线」通过分割线的位置计算中位数。边界处理必须处理分割点在数组两端的情况用无穷大 / 无穷小代替避免数组越界。分割点计算j (m n 1) / 2 - i是核心公式保证左右两部分元素个数相等或差 1。奇偶长度统一处理通过totalLeft (m n 1) / 2让奇数长度时左部分多 1 个统一中位数计算逻辑。三、算法思想对比与学习路径表格算法核心思想适用场景时间复杂度栈Stack后进先出LIFO括号匹配、逆序、DFS、表达式求值O(n)二分查找分治每次缩小一半范围有序数组查找、中位数计算O(logn)学习建议栈的学习先掌握「有效括号」这道基础题再进阶到「最长有效括号」「柱状图中最大的矩形」等难题彻底吃透栈的应用。二分查找的学习先掌握基础有序数组的二分查找再进阶到旋转数组、中位数等难题重点理解「分割线」的思想。四、总结有效括号栈的经典入门题核心是利用栈的后进先出特性匹配括号是学习栈的必刷题。寻找两个正序数组的中位数二分查找的天花板难题核心是通过二分查找找到分割线将两个数组分成左右两部分从而计算中位数是算法面试的高频难题。