栈与队列 | part02

150. 逆波兰表达式求值 - 力扣LeetCode给你一个字符串数组 tokens 表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。注意有效的算符为 、-、* 和 / 。每个操作数运算对象都可以是一个整数或者另一个表达式。两个整数之间的除法总是 向零截断 。表达式中不含除零运算。输入是一个根据逆波兰表示法表示的算术表达式。答案及所有中间计算结果可以用 32 位 整数表示。示例 1输入tokens [2,1,,3,*]输出9解释该算式转化为常见的中缀算术表达式为((2 1) * 3) 9示例 2输入tokens [4,13,5,/,]输出6解释该算式转化为常见的中缀算术表达式为(4 (13 / 5)) 6示例 3输入tokens [10,6,9,3,,-11,,/,,17,,5,]输出22解释该算式转化为常见的中缀算术表达式为((10 * (6 / ((9 3) * -11))) 17) 5 ((10 * (6 / (12 * -11))) 17) 5 ((10 * (6 / -132)) 17) 5 ((10 * 0) 17) 5 (0 17) 5 17 5 22public int evalRPN(String[] tokens) { DequeInteger stack new ArrayDeque(); for (int i 0; i tokens.length; i) { String token tokens[i]; if (token.equals()) { stack.push(stack.pop() stack.pop()); }else if (token.equals(-)) { stack.push(-stack.pop() stack.pop()); }else if (token.equals(*)) { stack.push(stack.pop() * stack.pop()); }else if (token.equals(/)) { int first stack.pop(); int second stack.pop(); stack.push(second / first); }else { stack.push(Integer.parseInt(token)); } } return stack.pop(); }解题逆波兰表达式Reverse Polish Notation, RPN也称为后缀表达式是一种将运算符写在操作数之后的表达式表示法。例如中缀表达式(1 2) * 3对应的逆波兰表达式为[1, 2, , 3, *]。有效的运算符只有四个所以我们使用条件语句根据不同的运算符进行不同的操作。当我们遇到是数字的时候直接入栈即可遇到运算符再弹出数字进行操作这里需要注意的是运算顺序需要的是第二从栈中出来的数字在前先出栈的那个元素在后的顺序。还要注意的一点是我们的token是一个字符串数组所以我们入栈的时候需要进行转换将其转换为Integer因为我们要用的是集合类集合类需要使用包装类。239. 滑动窗口最大值 - 力扣LeetCode给定一个数组 nums有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。提示1 nums.length 10^5-10^4 nums[i] 10^41 k nums.lengthpublic int[] maxSlidingWindow(int[] nums, int k) { int[] result new int[nums.length - k 1]; MyQueue myQueue new MyQueue(); int index 0; for (int i 0; i nums.length; i) { if (i k) { myQueue.poll(nums[i - k]); } myQueue.add(nums[i]); if (i k - 1) { result[index] myQueue.peek(); } } return result; } class MyQueue { DequeInteger deque new LinkedList(); //弹出元素时比较当前要弹出的数值是否等于队列出口的数值如果相等则弹出 //同时判断队列当前是否为空 void poll(int val) { if (!deque.isEmpty() val deque.peek()) { deque.poll(); } } //添加元素时如果要添加的元素大于入口处的元素就将入口元素弹出 //保证队列元素单调递减 //比如此时队列元素3,12将要入队比1大所以1弹出此时队列3,2 void add(int val) { while (!deque.isEmpty() val deque.getLast()) { deque.removeLast(); } deque.add(val); } //队列队顶元素始终为最大值 int peek() { return deque.peek(); } }什么是单调队列普通的队列是“先进先出”但单调队列在保持“先进先出”特性的基础上强行让队列内部的元素保持单调递减的顺序队头最大队尾最小。为了维持这个顺序它在入队和出队时做了特殊的逻辑处理入队时如果新来的元素比队尾的元素大说明队尾那些较小的元素“没戏了”因为它们既比新元素小又比新元素早过期所以要把它们删掉。出队时只有当要移出的元素正好是队头元素时才真正执行删除操作。单调队列中存储的是数组的下标。在进行遍历的时候先判断队列头部的元素是否是过期元素就是当前头部元素小于要入队的元素即将要离开窗口如果是则移除随后我们需要保持剩下队列的单调性因为我们需要入队新元素需要维护单调性会进行多次移除元素随后再入队元素。这个时候若下标超过k-1说明窗口形成可以将结果存入结果中。public int[] maxSlidingWindow(int[] nums, int k) { int n nums.length; int[] ans new int[n - k 1]; // 双端队列存的是【下标】 DequeInteger dq new ArrayDeque(); for (int i 0; i n; i) { // 1. 弹出“滑出窗口”的下标处理过期元素 while (!dq.isEmpty() dq.peek() i - k 1) { dq.poll(); } // 2. 保持单调递减从队尾弹走比当前值小的下标 while (!dq.isEmpty() nums[dq.peekLast()] nums[i]) { dq.pollLast(); } // 3. 当前下标入队 dq.offer(i); // 4. 当窗口成型时队头就是最大值 if (i k - 1) { ans[i - k 1] nums[dq.peek()]; } } return ans; }第二种解法是利用双端队列去实现单调队列具体的实现看代码细节。347. 前 K 个高频元素 - 力扣LeetCode给定一个非空的整数数组返回其中出现频率前 k 高的元素。示例 1:输入: nums [1,1,1,2,2,3], k 2输出: [1,2]示例 2:输入: nums [1], k 1输出: [1]提示你可以假设给定的 k 总是合理的且 1 ≤ k ≤ 数组中不相同的元素的个数。你的算法的时间复杂度必须优于 $O(n \log n)$ , n 是数组的大小。题目数据保证答案唯一换句话说数组中前 k 个高频元素的集合是唯一的。你可以按任意顺序返回答案。public int[] topKFrequent(int[] nums, int k) { MapInteger, Integer map new HashMap(); // 统计频率 for (int i 0; i nums.length; i) { map.put(nums[i], map.getOrDefault(nums[i], 0) 1); } PriorityQueueInteger[] pq new PriorityQueue((pair1, pair2) - pair1[1] - pair2[1]); for (Map.EntryInteger, Integer entry : map.entrySet()) { if (pq.size() k) { pq.offer(new Integer[] { entry.getKey(), entry.getValue() }); } else { if (entry.getValue() pq.peek()[1]) { pq.poll(); pq.offer(new Integer[] { entry.getKey(), entry.getValue() }); } } } int[] res new int[k]; for (int i k - 1; i 0; i--) { res[i] pq.poll()[0]; } return res; }解题数字出现的频率可以用map去进行统计而我们的顺序则是需要用到一种结构优先级队列我们普通的队列是遵循先进先出的规则而优先级队列则是优先级高的先出队特点入队顺序无关紧要。出队顺序严格按照优先级排序。通常用于任务调度紧急任务先做、Dijkstra 最短路径算法、哈夫曼编码等。而优先级队列的底层则是通过堆的这种结构一种特殊的完全二叉树。堆主要分为了大顶堆和小顶堆区别在于大的排在顶部还是小的排在顶部大顶堆适用于快速访问最大值小顶堆则相反。堆这种结构很适合插入和删除就跟树是一样的。注意虽然插入和删除是 O(log⁡N)O(logN) 但如果你要遍历堆中所有元素并排序那是 O(Nlog⁡N)O(NlogN) 。堆本身不是有序数组除了堆顶其他元素之间没有严格的大小顺序比如左孩子和右孩子之间谁大谁小是不确定的。为什么选择“小顶堆”这是本题的精华所在。方案 A全排序将所有元素按频率排序取前K个。时间复杂度 O(Nlog⁡N)O(NlogN) 。如果 N109,K5N109,K5 这样做太浪费了。方案 B大顶堆将所有元素放入大顶堆弹出K次。建堆 O(N)O(N) 弹出K次 O(Klog⁡N)O(KlogN) 。总复杂度 O(NKlog⁡N)O(NKlogN) 。当 KK接近 NN时退化为 O(Nlog⁡N)O(NlogN) 。方案 C小顶堆本代码采用维护一个大小为K的小顶堆。堆中始终只保留当前遇到的频率最高的K个元素。堆顶是这 KK个元素中频率最小的守门员。遍历过程中如果遇到一个新元素其频率大于堆顶元素的频率说明堆顶不配留在前 KK名将其踢出新元素入堆。时间复杂度 O(Nlog⁡K)O(NlogK) 。因为堆的大小始终限制为 KK每次调整堆只需 log⁡KlogK。当 K≪NK≪N时效率极高。算法流程堆未满size k→ 直接丢进去。堆已满 → 拿当前元素的频次跟堆顶比如果更大说明堆顶不配留在 Top-k弹出堆顶把当前元素插进去否则丢弃当前元素堆不动。一趟下来堆里就保留了全局频次最高的 k 个元素堆顶是这 k 个里频次最小的。Java的Map.Entry在概念上确实非常类似于 C 中的std::pair。它们的核心作用都是将两个对象键 Key 和 值 Value捆绑在一起作为一个整体进行处理。不过它们在来源、使用场景和具体实现上有一些细微的区别。下面我为你详细拆解1. 核心对比JavaMap.Entryvs Cstd::pair特性JavaMap.EntryK, VCstd::pairT1, T2本质是一个接口 (Interface)是一个结构体/类模板 (Struct/Class Template)主要来源几乎专门用于Map的遍历 (entrySet())通用工具可用于任何需要存两个值的场景访问成员方法调用getKey(),getValue()直接访问成员first,second可变性Value 可修改(setValue())Key 通常不可改两个成员通常都可直接修改典型用法for (Map.EntryK,V e : map.entrySet())std::pairint, string p {1, a};2. 深入理解 Java 中的Map.Entry在 Java 中Entry不是一个独立存在的通用“二元组”类像 C 那样它是java.util.Map接口内部的一个静态嵌套接口。为什么需要它当你有一个HashMap时数据是分散存储的。如果你想同时高效地获取Key和Value而不是先拿 Key 再去查 Value你需要一种方式把它们“打包”拿出来。map.keySet()只给你 Key。map.values()只给你 Value。map.entrySet()给你一组Entry对象每个对象里都同时包含了 Key 和 Value。代码示例MapString, Integer map new HashMap(); map.put(Apple, 10); map.put(Banana, 5); // entrySet() 返回的是一个 SetMap.EntryString, Integer for (Map.EntryString, Integer entry : map.entrySet()) { // 类似 C 的 p.first String key entry.getKey(); // 类似 C 的 p.second Integer value entry.getValue(); System.out.println(key : value); // 特有功能可以直接修改当前 Entry 的 Value (C pair 也可以直接改) // 这比 map.put(key, newValue) 更高效因为不需要重新哈希查找 entry.setValue(20); }关键点它是接口你不能直接new Map.Entry...()。你拿到的Entry对象通常是 Map 内部类如HashMap.Node实现的实例。生命周期Entry对象通常是在遍历过程中临时使用的。如果在遍历结束后还持有某个Entry引用并且原 Map 发生了结构变化如 remove 了该 key这个Entry可能会失效取决于具体 Map 实现。如何手动创建二元组如果你只是想在 Java 里随便存两个值不像 C 那样随处可用pairJava 标准库没有直接的Pair类直到 Java FX 才有或者 Apache Commons 库里有。现代 Java (Java 9)通常直接用List.of(k, v)或自定义记录类record Pair(K k, V v) {}。旧版 Java很多人会自己写一个简单的类或者用AbstractMap.SimpleEntryK, V这是 JDK 提供的唯一可直接实例化的 Entry 实现类。// 如果你真的需要一个独立的 Entry 对象类似 C pair Map.EntryString, Integer myPair new AbstractMap.SimpleEntry(Age, 25); System.out.println(myPair.getKey()); // Age System.out.println(myPair.getValue()); // 253. 深入理解 C 中的std::pair在 C 中std::pair是一个非常通用的工具不仅仅用于 Map。通用性你可以用它来返回两个值、存储坐标(x, y)、或者作为std::map的节点。语法糖C17 引入了结构化绑定让pair用起来更像原生类型。std::pairint, string p {1, Hello}; // 传统访问 cout p.first , p.second; // C17 结构化绑定 (非常爽) auto [id, name] p;Map 中的表现Cstd::map的迭代器解引用后得到的直接就是std::pairconst Key, Value。for (auto it myMap.begin(); it ! myMap.end(); it) { // it-first 是 Key (const) // it-second 是 Value } // 或者 C17 for (auto const [key, val] : myMap) { ... }4. 总结与类比场景C 写法Java 写法备注定义一个二元组std::pairint, int p(1, 2);var p new AbstractMap.SimpleEntry(1, 2);或record Pair(int k, int v){}Java 标准库较少直接用作通用二元组访问第一个元素p.firstp.getKey()Java 是方法调用访问第二个元素p.secondp.getValue()Java 是方法调用遍历 Mapfor (auto [k, v] : map)for (var e : map.entrySet())Java 必须通过entrySet()修改值p.second 10;p.setValue(10);Java 必须用 setter 方法结论是的你可以把Map.Entry理解为 Java 版本的std::pair但它更“专一”它主要服务于Map的遍历和操作。它通过方法 (getKey,getValue) 而不是公有成员变量来访问数据符合 Java 的封装习惯。如果你在 Java 代码中看到Entry99% 的情况都是在处理Map的键值对遍历。