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