★ FEATURED ARTICLE 1. 字符串解码栈的经典应用字符串解码问题LeetCode 394是栈数据结构的典型应用场景。给定一个编码字符串如3[a2[c]]我们需要将其解码为accaccacc。这个问题的关键在于处理嵌套结构而栈的先进后出特性恰好能完美解决嵌套解析的需求。1.1 核心算法思路整个解码过程可以分解为以下几个关键步骤双栈结构设计使用两个栈分别存储数字重复次数和字符串片段。数字栈处理多位数的累积字符串栈保存待组合的字符片段。遍历处理字符遇到数字时完整读取整个数字处理多位数情况遇到[时只是作为分隔符无需特殊处理遇到字母时直接压入字符串栈遇到]时触发解码操作解码操作细节弹出字符串栈中的元素直到遇到[反转这些字符串片段因为栈是先进后出弹出数字栈顶元素作为重复次数将重复后的字符串重新压入栈中1.2 代码实现解析class Solution { public String decodeString(String s) { DequeString strStack new ArrayDeque(); DequeInteger numStack new ArrayDeque(); for (int i 0; i s.length(); i) { // 处理数字 int num 0; while (Character.isDigit(s.charAt(i))) { num num * 10 s.charAt(i) - 0; i; } if (num ! 0) numStack.offerLast(num); // 处理字符 if (s.charAt(i) ! ]) { strStack.offerLast(s.charAt(i) ); } else { // 解码操作 ListString list new ArrayList(s.length()); while (!strStack.peekLast().equals([)) { list.add(strStack.pollLast()); } Collections.reverse(list); String str String.join(, list); strStack.pollLast(); // 弹出[ // 重复字符串 StringBuilder sb new StringBuilder(); int cnt numStack.pollLast(); for (int j 1; j cnt; j) { sb.append(str); } strStack.offerLast(sb.toString()); } } return String.join(, strStack); } }1.3 关键技巧与注意事项多位数字处理使用num num * 10 currentChar - 0来累积多位数字这是处理数字字符串的经典方法。字符串反转问题从栈中弹出的字符串片段是逆序的需要先收集到List中再反转。这里使用Collections.reverse()比直接操作StringBuilder更直观。性能优化点初始化List时指定容量避免扩容使用StringBuilder而不是直接字符串拼接双端队列(Deque)比Stack类性能更好边界情况空字符串输入没有嵌套的情况如3[a]深层嵌套如2[3[a]2[b]]数字为0的情况题目通常保证有效输入提示在实际面试中可以先用递归思路解释解法再优化为迭代栈的实现。递归虽然直观但可能有栈溢出风险。2. 每日温度单调栈的应用LeetCode 739题要求对于每一天的温度找出需要等待多少天才能遇到更暖和的温度。这是单调栈的经典应用场景。2.1 算法核心思想单调栈维护一个温度递减的序列。当遇到比栈顶温度高的天数时就可以确定栈顶元素的结果初始化结果数组为0使用栈保存尚未找到更高温度的天数索引遍历温度数组当前温度 栈顶温度时计算天数差并记录结果否则将当前天数入栈2.2 代码实现class Solution { public int[] dailyTemperatures(int[] temperatures) { int[] res new int[temperatures.length]; DequeInteger stack new ArrayDeque(); for (int i 0; i temperatures.length; i) { while (!stack.isEmpty() temperatures[stack.peekLast()] temperatures[i]) { int index stack.pollLast(); res[index] i - index; } stack.offerLast(i); } return res; } }2.3 关键点分析单调栈性质保持栈内元素对应的温度值单调递减这样遇到更高温度时就可以批量处理栈中元素。索引存储栈中存储的是天数索引而非温度值方便计算天数差。时间复杂度O(n)每个元素最多入栈出栈一次。空间复杂度O(n)最坏情况下所有元素都入栈。3. 柱状图中最大矩形单调栈进阶LeetCode 84题要求在柱状图中找出面积最大的矩形。这需要为每个柱子找到左右边界。3.1 算法思路左右边界数组left[i]第i个柱子左边第一个比它矮的柱子索引right[i]第i个柱子右边第一个比它矮的柱子索引单调栈维护使用单调递增栈来高效确定每个柱子的边界。面积计算对于每个柱子面积为height[i] * (right[i] - left[i] - 1)3.2 代码实现class Solution { public int largestRectangleArea(int[] heights) { int[] left new int[heights.length]; int[] right new int[heights.length]; Arrays.fill(right, heights.length); DequeInteger stack new ArrayDeque(); for (int i 0; i heights.length; i) { while (!stack.isEmpty() heights[stack.peekLast()] heights[i]) { right[stack.pollLast()] i; } left[i] stack.isEmpty() ? -1 : stack.peekLast(); stack.offerLast(i); } int result 0; for (int i 0; i heights.length; i) { result Math.max(result, (right[i] - left[i] - 1) * heights[i]); } return result; } }3.3 注意事项右边界初始化初始化为数组长度处理没有右边更小柱子的情况。左边界处理栈为空时设为-1表示左边没有更小的柱子。单调栈性质维护栈内柱子高度单调递增遇到更矮柱子时确定右边界。4. 数组中第K个最大元素快速选择算法LeetCode 215题要求找出未排序数组中第K个最大的元素。这可以通过改造快速排序来实现。4.1 快速选择算法分区操作选择一个pivot将数组分为两部分。选择方向根据pivot位置决定继续处理左半还是右半。时间复杂度平均O(n)最坏O(n^2)但可以通过随机化pivot避免。4.2 代码实现class Solution { public int findKthLargest(int[] nums, int k) { return quickSelect(nums, 0, nums.length - 1, nums.length - k); } private int quickSelect(int[] nums, int left, int right, int k) { if (left right) return nums[left]; int pivotIndex partition(nums, left, right); if (k pivotIndex) { return nums[k]; } else if (k pivotIndex) { return quickSelect(nums, left, pivotIndex - 1, k); } else { return quickSelect(nums, pivotIndex 1, right, k); } } private int partition(int[] nums, int left, int right) { int pivot nums[right]; int i left; for (int j left; j right; j) { if (nums[j] pivot) { swap(nums, i, j); i; } } swap(nums, i, right); return i; } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; } }4.3 算法优化随机化pivot避免最坏情况时间复杂度。三路快排处理大量重复元素的情况。堆方法使用大小为K的最小堆适合海量数据场景。5. 前K个高频元素基于快速选择LeetCode 347题要求统计元素频率并返回频率最高的K个元素。5.1 解决方案频率统计使用HashMap统计每个元素的出现次数。快速选择基于频率进行快速选择找出前K大的频率。结果收集根据选出的频率阈值收集结果。5.2 代码实现class Solution { public int[] topKFrequent(int[] nums, int k) { MapInteger, Integer frequencyMap new HashMap(); for (int num : nums) { frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) 1); } ListMap.EntryInteger, Integer entries new ArrayList(frequencyMap.entrySet()); quickSelect(entries, 0, entries.size() - 1, k - 1); int[] result new int[k]; for (int i 0; i k; i) { result[i] entries.get(i).getKey(); } return result; } private void quickSelect(ListMap.EntryInteger, Integer entries, int left, int right, int k) { if (left right) return; int pivotIndex partition(entries, left, right); if (pivotIndex k) { return; } else if (pivotIndex k) { quickSelect(entries, left, pivotIndex - 1, k); } else { quickSelect(entries, pivotIndex 1, right, k); } } private int partition(ListMap.EntryInteger, Integer entries, int left, int right) { int pivot entries.get(right).getValue(); int i left; for (int j left; j right; j) { if (entries.get(j).getValue() pivot) { Collections.swap(entries, i, j); i; } } Collections.swap(entries, i, right); return i; } }5.3 替代方案比较最小堆方法维护大小为K的最小堆时间复杂度O(nlogk)。桶排序适合频率范围不大的情况时间复杂度O(n)。快速选择平均O(n)空间复杂度O(n)适合一般情况。6. 数据流的中位数双堆技巧LeetCode 295题要求设计一个数据结构能不断添加数字并快速返回中位数。6.1 双堆设计最大堆存储较小的一半数字最小堆存储较大的一半数字平衡条件保证两个堆的大小差不超过16.2 代码实现class MedianFinder { PriorityQueueInteger maxHeap; // 存储较小的一半 PriorityQueueInteger minHeap; // 存储较大的一半 public MedianFinder() { maxHeap new PriorityQueue((a, b) - b - a); minHeap new PriorityQueue(); } public void addNum(int num) { maxHeap.offer(num); minHeap.offer(maxHeap.poll()); // 保持平衡 if (maxHeap.size() minHeap.size()) { maxHeap.offer(minHeap.poll()); } } public double findMedian() { if (maxHeap.size() minHeap.size()) { return maxHeap.peek(); } else { return (maxHeap.peek() minHeap.peek()) / 2.0; } } }6.3 操作步骤解析添加元素流程先加入最大堆将最大堆的堆顶移到最小堆如果最小堆更大再移回一个到最大堆中位数获取如果堆大小不等返回较大堆的堆顶否则返回两堆顶的平均值时间复杂度添加元素O(logn)查询中位数O(1)7. 买卖股票的最佳时机贪心算法LeetCode 121题要求在股票价格序列中找到最大利润。7.1 算法思路记录历史最低点遍历时维护遇到的最低价格。计算当前利润当前价格减去历史最低点。更新最大利润始终保持最大的利润值。7.2 代码实现class Solution { public int maxProfit(int[] prices) { int minPrice Integer.MAX_VALUE; int maxProfit 0; for (int price : prices) { if (price minPrice) { minPrice price; } else if (price - minPrice maxProfit) { maxProfit price - minPrice; } } return maxProfit; } }7.3 算法分析时间复杂度O(n)只需一次遍历。空间复杂度O(1)只使用常数空间。边界情况价格单调递减时利润为0空输入或单元素数组价格全部相同8. 跳跃游戏贪心策略LeetCode 55题判断是否能从数组起点跳到终点。8.1 算法思想维护最远可达位置遍历时更新能到达的最远位置。提前终止如果当前位置超过了最远可达位置说明无法继续前进。成功条件最远可达位置超过或等于终点。8.2 代码实现class Solution { public boolean canJump(int[] nums) { int maxReach 0; for (int i 0; i nums.length; i) { if (i maxReach) return false; maxReach Math.max(maxReach, i nums[i]); if (maxReach nums.length - 1) return true; } return true; } }8.3 关键点贪心性质只需要关心能到达的最远位置不需要关心具体路径。提前终止优化一旦发现无法继续前进就立即返回。边界处理空数组或单元素数组直接返回true。9. 跳跃游戏II最少跳跃次数LeetCode 45题要求找到跳到终点的最少跳跃次数。9.1 算法改进维护两个边界当前跳跃能到达的边界下一次跳跃能到达的最远边界跳跃时机到达当前边界时必须进行一次跳跃。9.2 代码实现class Solution { public int jump(int[] nums) { int jumps 0; int currentEnd 0; int farthest 0; for (int i 0; i nums.length - 1; i) { farthest Math.max(farthest, i nums[i]); if (i currentEnd) { jumps; currentEnd farthest; } } return jumps; } }9.3 算法分析时间复杂度O(n)一次遍历。空间复杂度O(1)。正确性证明每次跳跃都选择能到达的最远位置保证跳跃次数最少。10. 划分字母区间贪心哈希LeetCode 763题要求将字符串划分为尽可能多的片段同一字母只出现在一个片段中。10.1 算法步骤记录最后出现位置先遍历字符串记录每个字母的最后出现位置。维护区间边界遍历时更新当前区间的右边界。划分时机当遍历位置等于当前右边界时完成一个划分。10.2 代码实现class Solution { public ListInteger partitionLabels(String s) { int[] last new int[26]; for (int i 0; i s.length(); i) { last[s.charAt(i) - a] i; } ListInteger result new ArrayList(); int start 0, end 0; for (int i 0; i s.length(); i) { end Math.max(end, last[s.charAt(i) - a]); if (i end) { result.add(end - start 1); start end 1; } } return result; } }10.3 优化技巧数组替代HashMap字母数量有限时数组访问效率更高。单次遍历优化可以合并两次遍历但会降低代码可读性。结果存储直接存储片段长度而非子字符串节省空间。
阅读完成 · 觉得有帮助？
