宁波led网站建设,动漫网站怎么做,营销网站运营的基本环节,网站开发整体流程文章目录 前言1. 括号匹配问题2. 最小栈问题3. 最大栈 总结 前言 提示#xff1a;如果让我送给年轻人四个字#xff0c;就是#xff1a;量力而行。 量力而行不会失眠#xff0c;不会啃老#xff0c;不会为各种考试焦虑。顺其自然活得轻松。其实#xff0c;量力而行最易大… 文章目录 前言1. 括号匹配问题2. 最小栈问题3. 最大栈 总结 前言 提示如果让我送给年轻人四个字就是量力而行。 量力而行不会失眠不会啃老不会为各种考试焦虑。顺其自然活得轻松。其实量力而行最易大展宏图。 栈在常见的数据结构中也是比较常用的一些经典的题目对于理解栈很有帮助就那他们练手吧 1. 括号匹配问题
栈的典型题目栈常用在括号匹配表达式计算等等我看就来看看这个最经典的问题
参考题目介绍20. 有效的括号 - 力扣LeetCode 对于这个题目来说还是比较简单的要处理的问题难题时判断符号是否一组我们可以先用Hash将所有的符合存储下来左半边就做key右半边做value。遍历字符串的时候遇到左半边符号就入栈遇到右半边的符号就与栈顶的符号进行比较不匹配就返回false
public static boolean isValid(String s) {if (s.length() 2) {return false;}HashMapCharacter, Character map new HashMapCharacter, Character();map.put([, ]);map.put((, ));map.put({, });StackCharacter stack new Stack();for (int i 0; i s.length(); i) {char c s.charAt(i);if (map.containsKey(c)) {stack.push(c);} else {if (!stack.isEmpty()) {// 拿到栈顶的左括号Character left stack.pop();Character right map.get(left);if (right ! c) {return false;}} else {return false;}}}return stack.isEmpty();}
当然类似的题目还有很多有难有易可以多杀杀挫挫锐气哈哈哈这里我就不一一举例了
2. 最小栈问题
参考题目介绍155. 最小栈 - 力扣LeetCode 不知到你会不会和我一样题目还没理解什么意思的别慌那我们就来看看这个题要怎么解。我觉得本题的关键在于getMin()到底表示什么我们可以画一个图 我们看到这个图大致已经有了思路Min栈内中间-2元素对它的理解就是解题的关键。
题目要求在常数时间内获取到栈中的最小值也就是我们不能在getMin()的时候去计算而是直接返回值也就说只能在push和pop中做一些操作了。
栈的特性时先进后出这个很重要我们可以这么做我们将元素a存入栈中的时候就把当前的最小值m记录下来也就是说如果a时栈顶最小是就是m我们可以直接返回。
这样的话我们就可以设计一个数据结构使得每个元素a与其相应的最小值m时刻保持一致所以我们需要一个辅助栈与元素栈插入和删除保持一致用来存储每个元素对应的最小值。
当元素要入栈的时候我们取当前辅助栈的栈顶元素与之比较该元素小就将这个值存入辅助栈中当一个元素要出栈时我们把辅助栈的栈顶元素一并出栈
这样的话在任意时刻栈内元素的最小值就存储在辅助栈的栈顶元素中。
这样的话代码写起来就非常简单了
class MinStack {private static StackInteger xStack;private static StackInteger minStack;public MinStack() {xStack new Stack();minStack new Stack();// 占位符minStack.push(Integer.MAX_VALUE);}public void push(int val) {xStack.push(val);minStack.push(Math.min(val,minStack.peek()));}public void pop() {xStack.pop();minStack.pop();}public int top() {return xStack.peek();}public int getMin() {return minStack.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj new MinStack();* obj.push(val);* obj.pop();* int param_3 obj.top();* int param_4 obj.getMin();*/有最小栈那会不会有最大栈呢哈哈哈他来了
3. 最大栈
参考题目介绍716. 最大栈 - 力扣LeetCode
设计一个最大栈数据结构及支持栈操作有支持查找栈中最大元素。 这个题和上一题相反处理方法上一致一个普通的栈可以支持前三种操作push(x),pop()和top()这里我们需要考虑的是后面的操作peekMax()和popMax()。
对于peekMax()我们可以用另一个栈来存储每个位置对应的最大值比如第一个栈的元素为[2,1,5,3,9]那么第二个栈的元素就是[2,2,5,5,9]。在push(x)操作时只需要将第二个栈顶元素和x的最大值入栈就行而pop()操作只需要将第二个栈进行出栈。
对于popMax()由于我们指导当前栈中最大元素值我们就可以将两个栈同时出栈并存储第一个栈出栈的所有值。当某个时刻第一个栈中的出栈元素等于当前栈中的最大值时我们就找到了最大元素。此时我们将之前的第一个栈的所有元素重新入栈并同步更新到第二栈中就完成了popMax()操作
代码展示如下
import java.util.Stack;class MaxStack {public static StackInteger xStack;public static StackInteger maxStack;public MaxStack() {xStack new StackInteger();maxStack new StackInteger();}public void push(int val) {xStack.push(val);int max maxStack.isEmpty() ? val : maxStack.peek();maxStack.push(max val ? max : val);}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 StackInteger();while(top() ! max){stack.push(pop());}pop();while(!stack.isEmpty()){push(stack.pop());}return max;}}总结
提示栈的操作有时需要一个辅助栈来帮助解决问题。
