文章目录
- 用栈实现队列
- 用队列实现栈
- 有效的括号
- 我的解法
- 代码随想录
- 删除字符串中的所有相邻重复项
- 我的解法
- 代码随想录
- 栈解法
- 字符串充当栈
- ※双指针
- 逆波兰表达式求值
- 我的解法
- 代码随想录
- 滑动窗口最大值
- 我的解法
- 暴力解法
- 暴力解法+一点优化
- 单调队列
- 代码随想录
- 单调队列
- 前 K 个高频元素
- 代码随想录
- 优先队列
- 总结
用栈实现队列
https://leetcode.cn/problems/implement-queue-using-stacks/description/
在队列中，存入顺序是1、2、3，取出的顺序也是1、2、3。如果使用一个栈，那么取出顺序是3、2、1，如果想要和队列的取出顺序一致，那就要多使用一个新栈，3、2、1存入到新栈，从新栈中取出来就是1、2、3。
如果先push
1、2、3进栈，然后pop一次，接着存入4，再peek一次，需要怎么操作？
按照队列的操作逻辑，pop出来的应该是1，那就需要先将1、2、3按照顺序存入栈A中，然后从A中依次取出3、2、1，存储到栈B中（将这个行为称为转移），这时pop出来的就是1，栈B中剩余的元素是2、3；接着存入4，再peek的出来的应该是2，此时就不能从栈A中取出4放入到栈B中了，不然peek出来的是4，不是2，因此当栈B中有元素的时候，直接peek即可，无需进行转移操作
private Stack<Integer> stackA;
private Stack<Integer> stackB;public MyQueue() {this.stackA = new Stack<>();this.stackB = new Stack<>();
}public void push(int x) {this.stackA.push(x);
}public int pop() {transfer();return this.stackB.pop();
}public int peek() {transfer();return this.stackB.peek();
}/*** 转移栈A的元素到B中*/
private void transfer() {if (!stackB.empty()) {return;}while (!stackA.empty()) {stackB.push(stackA.pop());}
}public boolean empty() {// 当两个栈中的元素都为空时，队列才可以看成为空return this.stackA.empty() && this.stackB.empty();
}
用队列实现栈
https://leetcode.cn/problems/implement-stack-using-queues/description/
/*** @Author dam* @create 2023/11/1 22:06*/
public class MyStack {private LinkedList<Integer> queueA;private LinkedList<Integer> queueB;public MyStack() {this.queueA = new LinkedList<>();this.queueB = new LinkedList<>();}public void push(int x) {this.queueA.add(x);}public int pop() {int num;while (true) {Integer pop = queueA.pop();if (queueA.isEmpty()) {// --if-- queueA.isEmpty()==true，说明pop已经是queueA最后一个元素// 记录最后一个元素，这个元素要被弹出，无需存储到queueB中进行备份num = pop;break;} else {// --if-- 如果pop不是最后一个元素，那就将其存储到queueB中进行备份queueB.add(pop);}}// 将queueB中备份的元素重新添加回到queueA中while (!queueB.isEmpty()) {queueA.add(queueB.pop());}return num;}public int top() {int num;while (true) {Integer pop = queueA.pop();if (queueA.isEmpty()) {num = pop;queueB.add(pop);break;} else {queueB.add(pop);}}while (!queueB.isEmpty()) {queueA.add(queueB.pop());}return num;}public boolean empty() {return this.queueA.isEmpty();}}
有效的括号
https://leetcode.cn/problems/valid-parentheses/description/
【补充案例】
示例 4:
- 输入: “([)]”
- 输出: false
示例 5:
- 输入: “{[]}”
- 输出: true
我的解法
【思路】
使用一个栈来存储符号，遍历字符串的每个字符：
- 如果遍历到的是左括号，直接添加到栈中；
- 如果遍历到的是右括号，否则判断栈中的顶元素是否可以和当前所遍历右括号凑成一对，是则将栈顶元素消除，否则返回false，若栈为空也返回false
public static boolean isValid(String s) {if (s.length() % 2 == 1) {return false;}Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == ')') {if (stack.size() == 0 || stack.peek() != '(') {return false;} else {stack.pop();}} else if (c == '}') {if (stack.size() == 0 ||stack.peek() != '{') {return false;} else {stack.pop();}} else if (c == ']') {if (stack.size() == 0 ||stack.peek() != '[') {return false;} else {stack.pop();}} else {stack.add(c);}}return stack.size() == 0;
}
代码随想录
其实思路和我的一样，就是实现方法稍微有点不同
public boolean isValid(String s) {Deque<Character> deque = new LinkedList<>();char ch;for (int i = 0; i < s.length(); i++) {ch = s.charAt(i);//碰到左括号，就把相应的右括号入栈if (ch == '(') {deque.push(')');}else if (ch == '{') {deque.push('}');}else if (ch == '[') {deque.push(']');} else if (deque.isEmpty() || deque.peek() != ch) {return false;}else {//如果是右括号判断是否和栈顶元素匹配deque.pop();}}//最后判断栈中元素是否匹配return deque.isEmpty();
}
删除字符串中的所有相邻重复项
https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
我的解法
public String removeDuplicates(String s) {Stack<Character> stack = new Stack<>();char c;for (int i = 0; i < s.length(); i++) {c = s.charAt(i);if (stack.size() > 0 && stack.peek() == c) {stack.pop();} else {stack.add(c);}}StringBuilder stringBuilder = new StringBuilder();while (stack.size() > 0) {stringBuilder.insert(0, stack.pop());}return stringBuilder.toString();
}
代码随想录
栈解法
public String removeDuplicates(String S) {//ArrayDeque会比LinkedList在除了删除元素这一点外会快一点//参考：https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlistArrayDeque<Character> deque = new ArrayDeque<>();char ch;for (int i = 0; i < S.length(); i++) {ch = S.charAt(i);if (deque.isEmpty() || deque.peek() != ch) {deque.push(ch);} else {deque.pop();}}String str = "";//剩余的元素即为不重复的元素while (!deque.isEmpty()) {str = deque.pop() + str;}return str;
}
字符串充当栈
public String removeDuplicates(String s) {// 将 res 当做栈// 也可以用 StringBuilder 来修改字符串，速度更快StringBuffer res = new StringBuffer();// top为 res 的长度int top = -1;for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);// 当 top > 0,即栈中有字符时，当前字符如果和栈中字符相等，弹出栈顶字符，同时 top--if (top >= 0 && res.charAt(top) == c) {res.deleteCharAt(top);top--;// 否则，将该字符 入栈，同时top++} else {res.append(c);top++;}}return res.toString();
}
※双指针
public static String removeDuplicates(String s) {char[] ch = s.toCharArray();int fast = 0;int slow = 0;while (fast < s.length()) {// 直接用fast指针覆盖slow指针的值ch[slow] = ch[fast];// 遇到前后相同值的，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了if (slow > 0 && ch[slow] == ch[slow - 1]) {slow--;} else {slow++;}fast++;}return new String(ch, 0, slow);
}
【运行逻辑】
slow：0;fast：0
[a, b, b, a, c, a]
--------------------------------------------------
slow：1;fast：1
[a, b, b, a, c, a]
--------------------------------------------------
slow：2;fast：2
[a, b, b, a, c, a]
--------------------------------------------------
slow：1;fast：3
[a, b, b, a, c, a]
--------------------------------------------------
slow：0;fast：4
[a, a, b, a, c, a]
--------------------------------------------------
slow：1;fast：5
[c, a, b, a, c, a]
--------------------------------------------------
逆波兰表达式求值
https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
我的解法
注意：- / 需要特殊处理，要求：前面的元素 符号 后面的元素，但从栈中取出元素的时候，是先取出后面的元素
public int evalRPN(String[] tokens) {Stack<Integer> stack = new Stack<>();Integer pop;for (int i = 0; i < tokens.length; i++) {if (tokens[i].equals("+")) {stack.add(stack.pop() + stack.pop());} else if (tokens[i].equals("-")) {pop = stack.pop();stack.add(stack.pop() - pop);} else if (tokens[i].equals("*")) {stack.add(stack.pop() * stack.pop());} else if (tokens[i].equals("/")) {pop = stack.pop();stack.add(stack.pop() / pop);} else {stack.add(Integer.parseInt(tokens[i]));}}return stack.pop();
}
代码随想录
public int evalRPN(String[] tokens) {Deque<Integer> stack = new ArrayDeque();for (String s : tokens) {if ("+".equals(s)) { stack.push(stack.pop() + stack.pop()); } else if ("-".equals(s)) {stack.push(-stack.pop() + stack.pop());} else if ("*".equals(s)) {stack.push(stack.pop() * stack.pop());} else if ("/".equals(s)) {int temp1 = stack.pop();int temp2 = stack.pop();stack.push(temp2 / temp1);} else {stack.push(Integer.valueOf(s));}}return stack.pop();
}
Java中Deque和Stack哪个性能更好
通义千问：
Java中，
Deque接口通常被认为提供了比Stack类更好的性能。以下是几个理由：
- 底层实现优化：
Stack类继承自Vector，而Vector是一个历史悠久的类，它虽然线程安全，但采用了同步机制来确保线程安全性，这导致其在单线程环境下存在不必要的性能开销。对于不需要线程同步的栈操作，使用Stack可能会引入不必要的性能损耗。- 相比之下，
Deque接口的常见高效实现如ArrayDeque，不仅没有线程同步的开销（在单线程环境下），而且内部实现通常更为优化。ArrayDeque使用可变大小的数组来存储元素，它通过循环利用数组空间和移动元素来避免频繁的内存分配和释放，从而提供更快的插入和删除速度。- 扩容策略：
Vector（及其子类Stack）在需要扩容时通常会成倍增加容量，这意味着即使只是添加少量新元素也可能触发较大的内存重新分配和数据复制操作，这在某些场景下可能影响性能。ArrayDeque则采用更为灵活的扩容策略，它通常会以较小的增量增加容量，减少不必要的内存消耗和数据迁移。这种策略有助于保持更高的操作效率，特别是在栈操作频繁且元素数量变化不可预知的情况下。- 常量时间操作：
Deque接口保证了在两端进行push和pop操作的时间复杂度为O(1)，即常量时间复杂度。这意味着无论Deque大小如何，入栈和出栈操作都能在固定时间内完成。- 虽然
Stack作为Vector的子类理论上也能提供常量时间的push和pop操作，但由于上述的同步开销和可能的扩容问题，实际性能往往不如ArrayDeque。综上所述，在Java中，使用
Deque接口尤其是其高效实现ArrayDeque作为栈来使用，通常能获得比直接使用Stack类更好的性能。这主要是由于ArrayDeque没有不必要的线程同步开销、采用了更优化的扩容策略以及能够提供稳定的常量时间复杂度操作。因此，在非线程安全需求的栈应用场景中，推荐使用Deque（如ArrayDeque）代替Stack。
滑动窗口最大值
https://leetcode.cn/problems/sliding-window-maximum/description/
我的解法
暴力解法
每次都遍历窗口的所有元素来寻找最大值
public int[] maxSlidingWindow(int[] nums, int k) {int[] res = new int[nums.length - k + 1];for (int i = 0; i < nums.length - k + 1; i++) {res[i] = -10001;for (int j = 0; j < k; j++) {if (nums[i + j] >= res[i]) {res[i] = nums[i + j];}}}return res;
}
时间复杂度：O(n x k)
空间复杂度：O(n)
暴力解法+一点优化
这个版本加了一点点优化，就是记录窗口里面最大值所对应的索引。
当窗口移动的时候，判断移出窗口的元素索引是否为最大值所对应的索引？
- 是，说明窗口的最大值被移出，下一个窗口需要遍历全部元素来找到最大值
- 否，则窗口的最大值没变，只需要和新加入窗口的元素比大小即可
使用该方式，可以减少内部遍历的次数，优化一点时间复杂度：
public int[] maxSlidingWindow(int[] nums, int k) {int[] res = new int[nums.length - k + 1];// 最小值是根据取值范围来确定的int min = -10001;int max = min;int maxIndex = -1;for (int i = 0; i < nums.length - k + 1; i++) {if (max == min) {// --if-- 最大值丢失，需要完整遍历窗口的元素来选择最大值for (int j = 0; j < k; j++) {// 对于相同的最大值，记录最大的索引，这样才能在窗口移动的时候，尽量保证窗口的最大值还在if (nums[i + j] >= max) {max = nums[i + j];maxIndex = i + j;}}} else {// --if-- 上一个窗口的最大值还在，只需要对比新加入窗口的元素和最大值的大小即可if (nums[i + k - 1] >= max) {max = nums[i + k - 1];maxIndex = i + k - 1;}}res[i] = max;if (i == maxIndex) {// --if-- 移出窗口的元素就是当前窗口的最大值，最大值丢失max = min;}}return res;
}
单调队列
加入元素时，维持一个单调递减队列，每次获取最大值的时候，只需要获取队列的头部元素即可
案例
如num={1,3,1,2,0,5} k=3
- [1 3 1] 2 0 5 单调队列：[3 1]
- 1 [3 1 2] 0 5 单调队列：[3 2]
- 1 3 [1 2 0] 5 单调队列：[2 0]
- 1 3 1 [2 0 5] 单调队列：[5]
public int[] maxSlidingWindow(int[] nums, int k) {int[] res = new int[nums.length - k + 1];Deque<Integer> deque = new ArrayDeque<>();for (int i = 0; i < k - 1; i++) {addToDeque(deque, nums[i]);}for (int i = 0; i < nums.length - k + 1; i++) {addToDeque(deque, nums[i + k - 1]);res[i] = deque.peekFirst();if (deque.peekFirst() == nums[i]) {deque.pollFirst();}}return res;
}private void addToDeque(Deque<Integer> deque, int num) {while (!deque.isEmpty() && deque.peekLast() < num) {deque.pollLast();}deque.addLast(num);
}
代码随想录
单调队列
public int[] maxSlidingWindow(int[] nums, int k) {ArrayDeque<Integer> deque = new ArrayDeque<>();int n = nums.length;int[] res = new int[n - k + 1];int idx = 0;for(int i = 0; i < n; i++) {// 根据题意，i为nums下标，是要在[i - k + 1, i] 中选到最大值，只需要保证两点// 1.队列头结点需要在[i - k + 1, i]范围内，不符合则要弹出while(!deque.isEmpty() && deque.peek() < i - k + 1){deque.poll();}// 2.既然是单调，就要保证每次放进去的数字要比末尾的都大，否则也弹出while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {deque.pollLast();}deque.offer(i);// 因为单调，当i增长到符合第一个k范围的时候，每滑动一步都将队列头节点放入结果就行了if(i >= k - 1){res[idx++] = nums[deque.peek()];}}return res;
}
前 K 个高频元素
https://leetcode.cn/problems/top-k-frequent-elements/description/
代码随想录
优先队列
public static int[] topKFrequent(int[] nums, int k) {HashMap<Integer, Integer> numAndFrequencyMap = new HashMap<>();for (int num : nums) {
// if (numAndFrequencyMap.containsKey(num)) {
// numAndFrequencyMap.replace(num, numAndFrequencyMap.get(num) + 1);
// } else {
// numAndFrequencyMap.put(num, 1);
// }// 上面的代码可以用这一行来替代numAndFrequencyMap.put(num, numAndFrequencyMap.getOrDefault(num, 0) + 1);}PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue = new PriorityQueue<>((e1, e2) ->e2.getValue() - e1.getValue());for (Map.Entry<Integer, Integer> entry : numAndFrequencyMap.entrySet()) {priorityQueue.add(entry);}int[] res = new int[k];for (int i = 0; i < k; i++) {res[i] = priorityQueue.poll().getKey();}return res;
}
总结
- 遇到对称题，可以先想到使用栈
