建设网站赚钱的方法,价目表海报app制作,上海市建设部注册中心网站,深圳建设局网站深业中城绿化项目目录 括号匹配问题最小栈最大栈 最大栈和最小栈是极致栈的两个重要变种。最大栈用于存储当前匹配的最大值#xff0c;而最小栈用于存储当前匹配的最小值。
括号匹配问题
这个问题我们来看力扣20题的描述#xff1a; 给定一个只包括 ‘(’#xff0c;‘)’#xff0c;‘{’… 目录 括号匹配问题最小栈最大栈 最大栈和最小栈是极致栈的两个重要变种。最大栈用于存储当前匹配的最大值而最小栈用于存储当前匹配的最小值。
括号匹配问题
这个问题我们来看力扣20题的描述 给定一个只包括 ‘(’‘)’‘{’‘}’‘[’‘]’ 的字符串 s 判断字符串是否有效。
有效字符串需满足
左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 示例 1 输入s “()” 输出true 示例 2 输入s “()[]{}” 输出true 示例 3 输入s “(]” 输出false 对于这个题我们有两种解决思路 1.我们用哈希表把所有符号先存储起来左边符号作key右边符号作value。遍历字符串的时候遇见左边符号就入栈遇见右边符号就与栈顶的符号进行比较不匹配就返回false。 public boolean isValid(String s) {//获取字符串长度int n s.length();//如果字符串长度为奇数则返回falseif (n % 2 1) {return false;}//创建一个HashMap用于存储字符串中的括号MapCharacter, Character map new HashMap();map.put([, ]);map.put((, ));map.put({, });//创建一个栈用于存储字符串中的括号StackCharacter stack new Stack();//遍历字符串中的每一个字符for (int i 0; i s.length(); i) {char item s.charAt(i);//如果字符串中的字符在HashMap中存在则将其压入栈中if (map.containsKey(item)) {stack.push(item);} else {//如果栈不为空则弹出栈顶元素如果弹出的元素与当前字符串中的字符不匹配则返回falseif (stack.isEmpty() false) {char pop stack.pop();if (map.get(pop) ! item) {return false;}} else {return false;}}}//如果栈为空则返回true否则返回falsereturn stack.isEmpty();}单纯的使用栈如果遇见左边符号直接压入栈中遇见右边的符号是先判断栈是否为空为空则返回false不为空则弹出栈顶元素如栈顶元素不为相匹配的左边符号则直接返回false最后元素遍历完返回栈是否为空。
public boolean isValid(String s) {int n s.length();// 如果字符串长度为奇数则直接返回falseif (n % 2 1) {return false;}// 创建一个栈DequeCharacter stack new LinkedList();// 遍历字符串for (int i 0; i s.length(); i) {char c s.charAt(i);// 如果当前字符为左括号则将其压入栈中if (c ( | c [ || c {) {stack.push(c);// 如果当前字符为右括号则从栈中弹出一个元素如果弹出的元素与当前字符不匹配则返回false} else if (c } || c ] || c )) {if (stack.isEmpty()) {return false;}char top stack.pop();if ((top ! ( c )) || (top ! { c }) || (top ! [ c ])) {return false;}}}// 如果栈为空则返回true否则返回falsereturn stack.isEmpty();}最小栈
我们来看力扣155题的描述 设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。
这个题通俗的理解就是给栈提供一个能获取最小元素的方法并且要在常数时间内。 我们可以设计一个辅助栈与元素栈同步插入与删除用于存储每个元素入栈时的最小值也就是说在辅助栈中我们每次插入的是元素栈中的最小值
当一个元素要入栈时我们取当前辅助栈的栈顶存储的最小值与当前要入栈的元素中的最小值插入辅助栈中。当一个元素要出栈时我们把辅助栈的栈顶元素也一并弹出。 我们来看具体实现代码
class MinStack {// 定义两个双端队列分别存放输入的值和当前的最小值DequeInteger xStack;DequeInteger minStack;public MinStack() {// 初始化双端队列xStack new LinkedList();minStack new LinkedList();// 第一个最小值设置为最大值minStack.push(Integer.MAX_VALUE);}public void push(int val) {// 输入一个值xStack.push(val);// 将当前的最小值和输入的值比较取较小的值minStack.push(Math.min(minStack.peek(), val));}public void pop() {// 弹出双端队列的最后一个值xStack.pop();minStack.pop();}public int top() {// 返回双端队列的最后一个值return xStack.peek();}public int getMin() {// 返回双端队列的最小值return minStack.peek();}
}最大栈
跟最小栈实现方法类似寻找最大值。 需要注意的就是最后一个方法弹出最大值具体就是拿到最大元素然后在数字栈中把最大值以上的元素全部弹出存储在新建的栈中然后弹出最大值最后把新建的栈中的元素重新压入数字栈中。 由于力扣最大栈是VIP题目我们可以尝试一下牛客的最大栈问题。
class MaxStack {// 定义两个栈一个用来存储数字另一个用来存储最大值DequeInteger xStack;DequeInteger maxStack;public MaxStack() {// 初始化两个栈xStack new LinkedList();maxStack new LinkedList();}public void push(int val) {// 获取当前最大值如果栈为空则最大值为当前值int max maxStack.isEmpty() ? val : maxStack.peek();// 比较当前值和最大值取最大值max max val ? max : val;// 将值和最大值分别压入栈中xStack.push(val);maxStack.push(max);}public int pop() {// 弹出最大值栈顶元素maxStack.pop();// 弹出数字栈顶元素return xStack.pop();}public int top() {// 返回数字栈顶元素return xStack.peek();}public int peekMax() {// 返回最大值栈顶元素return maxStack.peek();}public int popMax() {// 获取最大值栈顶元素int max peekMax();// 创建一个栈StackInteger stack new Stack();// 当栈顶元素不等于最大值时将栈顶元素压入栈中while (top() ! max) {stack.push(pop());}// 弹出数字栈顶元素pop();// 将栈中的元素弹出压入数字栈中while (!stack.isEmpty()) {push(stack.pop());}// 返回最大值return max;}}
