【算法训练营Day10】栈与队列part2
文章目录
- 逆波兰表达式求值
- 滑动窗口最大值
- 前 K 个高频元素
逆波兰表达式求值
题目链接:150. 逆波兰表达式求值
解题逻辑:
- 遍历字符串数组
- 遇到数字就压栈
- 遇到符号就把栈顶的两个元素弹出来进行运算,算完之后再把结果压栈
- 如此循环往复直到遍历完整个字符串数组
代码如下:
class Solution {public int evalRPN(String[] tokens) {Deque<String> box = new ArrayDeque<>();for(String s : tokens) {if(s.equals("+")) box.push(Integer.toString(Integer.parseInt(box.pop()) + Integer.parseInt(box.pop()))); else if (s.equals("-")) box.push(Integer.toString( - (Integer.parseInt(box.pop()) - Integer.parseInt(box.pop())))); else if (s.equals("*")) box.push(Integer.toString(Integer.parseInt(box.pop()) * Integer.parseInt(box.pop()))); else if (s.equals("/")) {int a = Integer.parseInt(box.pop());int b = Integer.parseInt(box.pop());box.push(Integer.toString( b / a )); }else box.push(s);}return Integer.parseInt(box.pop());}
}
滑动窗口最大值
题目链接:239. 滑动窗口最大值
解题思路:
这道题我最先开始想的是使用优先级队列,但是优先级队列无法维护动态窗口的增添元素(因为优先级队列的底层是堆,添加进去就已经排好序了)。为了解决本题,我们应该使用另一种数据结构 – 单调队列。
这两种队列的概念如下:
单调队列
- 单调队列是一种特殊的队列,队列中的元素保持单调递增或递减。它的特点是:
- 元素有序:队列中的元素始终保持单调性。
- 高效操作:插入和删除操作都能保持队列的单调性,时间复杂度为 O (1)。
- 滑动窗口问题:常用于解决滑动窗口的最大值或最小值问题。
优先级队列
- 优先级队列是一种抽象数据类型,元素按照优先级排序,优先级高的元素先出队。它的特点是:
- 元素无序:元素按照优先级排序,但不保证完全有序。
- 高效操作:插入和删除操作的时间复杂度为 O (log n)。
- 贪心算法:常用于解决最优化问题,如 Dijkstra 算法。
那么我们如何保持单调队列的单调呢?
其核心就在于两个操作,例如现在我们需要维护一个单调递减的队列:
- add操作:我们只需要在push一个新元素进去的时候比较队尾的元素是否比队尾新进的元素要小(或等于),如果小(或等于)的话就入队,如果大的话就剔除队尾元素,直到队尾元素比新进元素要小
- remove操作:如果要删除的元素是最大元素(也就是队头元素),那么就执行remove操作,否则不进行操作
解题逻辑如下:
- 初始化两个指针代表窗口的两侧
- 初始化一个单调队列
- 将k个元素加入到队列中
- 随着窗口移动,根据指针进行元素的添加与剔除(如果窗口移除的元素value等于单调队列的出口元素,那么队列弹出元素,否则不用任何操作),并且将每次队头元素存储到数组中
- 返回数组
代码如下:
class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int[] result = new int[nums.length - k + 1];int left = 0;int right = k - 1;MonotonousQueue queue = new MonotonousQueue();for(int i = 0;i < k;i++) queue.add(nums[i]);int pointer = 0; while(right < nums.length) {result[pointer++] = queue.element();if(nums[left] == queue.element()) queue.remove();left++;right++;if(right < nums.length) queue.add(nums[right]);}return result;}class MonotonousQueue {Deque<Integer> myQueue = new ArrayDeque<>();public void add(Integer item){while(!myQueue.isEmpty() && myQueue.peekLast() < item) myQueue.pollLast(); myQueue.add(item);}public Integer remove(){return myQueue.remove();}public Integer element(){return myQueue.element();}}
}
前 K 个高频元素
题目链接:347. 前 K 个高频元素
解题思路:
- 使用hashmap进行计数
- 定义一个对象,用于存储元素以及次数
- 遍历hashmap创建对象放入到优先级队列中
- 从优先级队列中弹出k个元素形成数组所谓结果
代码如下:
class Solution {public int[] topKFrequent(int[] nums, int k) {PriorityQueue<CountHelper> pq = new PriorityQueue<>(Comparator.comparingInt(CountHelper::getCount).reversed());Map<Integer,Integer> countMap = new HashMap<>();for(int i = 0;i < nums.length;i++) countMap.put(nums[i],countMap.getOrDefault(nums[i],0) + 1);for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {Integer key = entry.getKey();Integer value = entry.getValue();pq.add(new CountHelper(key,value));}int[] result = new int[k];int pointer = 0;while(pointer < k) result[pointer++] = pq.remove().getNum();return result;}class CountHelper {private int num;private int count;public CountHelper(int n, int c){num = n;count = c;}public int getNum(){return num;}public int getCount(){return count;}public void setNum(int n){num = n;}public void setCount(int c){count = c;}}
}