括号匹配问题
描述 :
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
题目 :
LeetCode 20.有效的括号 :
20. 有效的括号
分析 :
本题还是比较简单的，其中比较麻烦的是如何判断两个符号是不是一组的，我们可以用哈希表将所有符号先存储，左半边做key,右半边做value。遍历字符串的时候，遇到左半边符号就入栈，遇到右半边符号就与栈顶的符号比较，不匹配就返回false
解析 :
LeetCode
class Solution {
public boolean isValid(String s) {
//创建栈
Stack<Character> sk = new Stack<>();
//创建Map
HashMap<Character,Character> map = new HashMap();
map.put('(',')');
map.put('[',']');
map.put('{','}');
for(int i =0; i< s.length();i++){
char c = s.charAt(i);
//如果是左边就压栈
if(map.containsKey(c)){
sk.push(c);
}else{
//否则就弹栈,看是否和左边匹配
if(!sk.isEmpty()){
if(c != map.get(sk.pop())){
return false;
}
}else{
//如果栈是空的就不匹配
return false;
}
}
}
//如果栈里是空的证明都匹配了 , 栈里不是空的证明有一个单的 不匹配
return sk.isEmpty();
}
}最小栈
描述 :
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
-
MinStack()初始化堆栈对象。 -
void push(int val)将元素val推入堆栈。 -
void pop()删除堆栈顶部的元素。 -
int top()获取堆栈顶部的元素。 -
int getMin()获取堆栈中的最小元素。
题目 :
LeetCode 155. 最小栈
分析 :
解题思路：
借用一个辅助栈 min_stack，用于存获取 stack 中最小值。
算法流程：
push() 方法： 每当push()新值进来时，如果 小于等于 min_stack 栈顶值，则一起 push() 到 min_stack，即更新了栈顶最小值；
pop() 方法： 判断将 pop() 出去的元素值是否是 min_stack 栈顶元素值（即最小值），如果是则将 min_stack 栈顶元素一起 pop()，这样可以保证 min_stack 栈顶元素始终是 stack 中的最小值。
getMin()方法： 返回 min_stack 栈顶即可。
min_stack 作用分析：
min_stack 等价于遍历 stack所有元素，把升序的数字都删除掉，留下一个从栈底到栈顶降序的栈。
相当于给 stack 中的降序元素做了标记，每当 pop() 这些降序元素，min_stack 会将相应的栈顶元素 pop() 出去，保证其栈顶元素始终是 stack 中的最小元素。
注意 : stack.pop().equals(minStack.peek()) 不要写成stack.pop() == minStack.peek()
这解法来自 : Krahets - 力扣（LeetCode）
代码 :文章来源：https://www.toymoban.com/news/detail-726567.html
class MinStack {
private Stack<Integer> stack;
private Stack<Integer> minStack;
public MinStack() {
this.stack = new Stack<>();
this.minStack = new Stack<>();
}
public void push(int val) {
if(minStack.isEmpty() || val <= minStack.peek()){
minStack.push(val);
}
stack.push(val);
}
public void pop() {
if(!stack.isEmpty() && stack.pop().equals(minStack.peek())){
minStack.pop();
}
}
public int top() {
return stack.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();
*/这关就到这里 , 下期一关见!文章来源地址https://www.toymoban.com/news/detail-726567.html
到了这里，关于算法通关村第四关-黄金挑战栈的经典问题的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
