【牛客刷题记录】【JAVA】栈

(1) 用两个栈实现队列

链接
很简单，如果有元素进入队列，则将其进入stack1。如果要出队列，那么就需要判断stack2的情况。人与法国stack2为空，则直接把stack1的元素全放进stack2（相当于顺序反过来），然后再出栈。如果不为空，则先出stack2的内容。

import java.util.*;
import java.util.Stack;public class Solution {Stack<Integer> stack1 = new Stack<Integer>();Stack<Integer> stack2 = new Stack<Integer>();public void push(int node) {stack1.add(node);}public int pop() {if(stack2.isEmpty()){while(!stack1.isEmpty()){stack2.add(stack1.pop());}}return stack2.pop();}
}

（2）包含min函数的栈

链接

pop和push的操作很简单，重点是在于min操作。如果直接设置一个min变量，确实可以记录最小值。但如果最小值出栈了，那么min就很难再修改。因此只有一个min是无法工作的，需要一个栈来同时记录，记录的内容为【当前元素入栈时的最小值】
例如，如：-2， 1， 3

stack1：-2 1 3
stack2：-2 -2 -2

如果-3入栈：

stack1：-2 1 3 -3
stack2：-2 -2 -2 -3

此时就可以得到当前的最小值。如果-3出栈，stack2的也进行pop操作，最小值也能被记录。时间复杂度是O(1)。

import java.util.*;
import java.util.Stack;public class Solution {Stack<Integer> s1=new Stack<>();Stack<Integer> s2=new Stack<>();int min=10001;public void push(int node) {s1.add(node);if(node<min){s2.add(node);min=node;}else{s2.add(min);}}public void pop() {s1.pop();s2.pop();min=s2.peek();}public int top() {return s1.peek();}public int min() {return s2.peek();}
}

（3）有效括号序列

链接

即用栈来存储字符串的内容，并且进行判断。如果匹配则出栈，否则不用出栈，最后判断栈是否为空。这样的做法是正确的，不过仍可以优化，因为可能出现（] 这样的情况，其实可以直接退出循环。不过这样写很简洁。

public boolean isValid (String s) {// write code hereStack<Character> stack=new Stack<>();for(char ch: s.toCharArray()){if(stack.isEmpty()){stack.push(ch);}else{if(ch==')'&&stack.peek()=='(' || ch==']'&&stack.peek()=='[' ||ch=='}'&&stack.peek()=='{'){stack.pop();}else{stack.push(ch);}}}return stack.isEmpty();}

我们可以优化一下，写得更复杂，或者用hash来存储映射关系。

public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (char ch : s.toCharArray()) {if (ch == '(' || ch == '[' || ch == '{') {stack.push(ch);} else if (ch == ')' && !stack.isEmpty() && stack.peek() == '(') {stack.pop();} else if (ch == ']' && !stack.isEmpty() && stack.peek() == '[') {stack.pop();} else if (ch == '}' && !stack.isEmpty() && stack.peek() == '{') {stack.pop();} else {return false;}}return stack.isEmpty();
}
// 或者这样
public boolean isValid(String s) {// 创建一个HashMap来存储括号的匹配关系Map<Character, Character> map = new HashMap<>();map.put(')', '(');map.put(']', '[');map.put('}', '{');// 创建一个栈Stack<Character> stack = new Stack<>();// 遍历字符串的每个字符for (char ch : s.toCharArray()) {// 如果字符是右括号if (map.containsKey(ch)) {// 弹出栈顶元素，如果栈为空则赋值为一个虚拟字符char topElement = stack.isEmpty() ? '#' : stack.pop();// 检查栈顶元素是否与当前字符的匹配字符相同if (topElement != map.get(ch)) {return false;}} else {// 如果字符是左括号，压入栈中stack.push(ch);}}// 如果栈为空，说明所有括号匹配return stack.isEmpty();
}

（4） 滑动窗口的最大值

链接
这题的做法其实比较固定，如果不暴力做就需要使用双端队列。
我们的队列元素大小总是非递增的，这样就可以很轻松的获取最大值。同时还要注意窗口内的元素达到3的情况。

假设数组是 [2, 3, 4, 2, 6, 2, 5, 1]，窗口大小是 3。

1. 初始化双端队列为空，结果列表为空。
2. 遍历数组：
   • 第一个元素 2：双端队列变为 [2]。
   • 第二个元素 3：移除 2，双端队列变为 [3]。
   • 第三个元素 4：移除 3，双端队列变为 [4]。窗口达到大小 3，最大值为 4。
   • 第四个元素 2：双端队列变为 [4, 2]。最大值仍为 4。
   • 第五个元素 6：移除 4 和 2，双端队列变为 [6]。最大值为 6。
   • 第六个元素 2：双端队列变为 [6, 2]。最大值仍为 6。
   • 第七个元素 5：移除 2，双端队列变为 [6, 5]。最大值仍为 6。
   • 第八个元素 1：双端队列变为 [6, 5, 1]。最大值为 6。

最终结果列表为 [4, 4, 6, 6, 6, 5]。

 public ArrayList<Integer> maxInWindows(int[] num, int size) {ArrayList<Integer> res = new ArrayList<>();if (num == null || size <= 0 || num.length < size) {return res;}Deque<Integer> deque = new LinkedList<>();for (int i = 0; i < num.length; i++) {// 移除不在滑动窗口范围内的元素if (i >= size && !deque.isEmpty() && deque.peekFirst() == num[i - size]) {deque.pollFirst();}// 移除所有小于当前元素的元素while (!deque.isEmpty() && deque.peekLast() < num[i]) {deque.pollLast();}// 添加当前元素deque.offerLast(num[i]);// 当窗口大小达到要求时，记录当前窗口的最大值if (i >= size - 1) {res.add(deque.peekFirst());}}return res;}

（4）最小的K个数

链接
最好想的就是直接排序再切片。

public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {// write code hereArrays.sort(input);ArrayList<Integer> result = new ArrayList<>();for (int i = 0; i < k; i++) {result.add(input[i]);}return result;}