当前位置：首页 > news >正文

算法训练营day11 栈与队列（栈的应用，单调队列，优先队列）

news 来源：原创 2024/9/20 8:15:20

💡 解题思路

📝 确定输入与输出
🔍 分析复杂度
🔨 复杂题目拆分 ：严谨且完整 地拆分为更小的可以解决的子问题（栈和队列的功能，栈和队列的变体应用）–（多总结）
💭 选择处理逻辑：根据拆分后的子问题，总结并选择合适的问题处理思路（单调队列，优先队列）
🔎 检查特殊情况：边界条件和特殊情况
🏁 返回结果

7. 逆波兰表达式求值 （栈的应用）

class Solution {public static int evalRPN(String[] tokens) {Set<Character> set = new HashSet<>();set.add('+');set.add('-');set.add('*');set.add('/');Stack<Integer> stack = new Stack<>();for (String token : tokens) {char c = token.charAt(0);if (token.length() == 1 && set.contains(c)) {if (stack.size() < 2) {  } else {int a = stack.pop();int b = stack.pop();stack.push(calculate(b, a, c));}} else {stack.push(Integer.parseInt(token));}}return stack.pop();}public static int calculate(int num1, int num2, char operation) {int result = 0;switch(operation) {case '+':result = num1 + num2;break;case '-':result = num1 - num2;break;case '*':result = num1 * num2;break;case '/':result = num1 / num2;break;default:}return result;}
}

239. 滑动窗口最大值(单调队列)

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n = nums.length;Deque<Integer> deque = new LinkedList<Integer>();for (int i = 0; i < k; i++) {while(!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {deque.pollLast();}deque.offerLast(i);}int[] ans = new int[n-k+1];ans[0] = nums[deque.peekFirst()];for (int i = k; i < n; i++) {while(!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {deque.pollLast();}deque.offerLast(i);while (deque.peekFirst() <= i - k) {deque.pollFirst();}ans[i-k+1] = nums[deque.peekFirst()];}return ans;}
}

347.前 K 个高频元素（优先队列）

class Solution {public int[] topKFrequent(int[] nums, int k) {Map<Integer, Integer> map = new HashMap<Integer, Integer>();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) + 1);}PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {public int compare(int[] m, int[] n) {return m[1] - n[1];}});for (Map.Entry<Integer, Integer> entry : map.entrySet()) {int num = entry.getKey(), count = entry.getValue();if (queue.size() == k) {if (queue.peek()[1] < count) {queue.poll();queue.offer(new int[] {num, count});}} else {queue.offer(new int[]{num, count});}}int[] res = new int[k];for (int i = 0; i < k; i++) {res[i] = queue.poll()[0];}return res;}
}