1. 有效的括号(lc20)
题目描述:
给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = “()”
输出：true
示例 2：
输入：s = “()[]{}”
输出：true
示例 3：
输入：s = “(]”
输出：false
提示：
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/valid-parentheses
解题思路：
可以使用一个栈来解决问题, 去遍历字符串s , 碰到左括号就将左括号字符就将字符入栈 , 碰到右括号字符此时再去看栈顶元素和右括号是否匹配, 遍历过程中可能会有以下情况出现,:
碰到右括号但栈中没有元素了(字符串还没遍历完栈中就没有元素了), 表明此时的右括号没有匹配的左括号;
碰到右括号, 栈顶是左括号但是和右括号种类不匹配,
碰到右括号, 栈顶是左括号且和和右括号种类匹配, 此时继续往后面遍历字符串;
字符串遍历完了但栈中还有元素, 此时栈中的左括号没有匹配的右括号
代码实现：
class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack(); for(int i = 0; i < s.length(); i++) { char ch1 = s.charAt(i); if(ch1=='(' || ch1=='[' || ch1=='{') { stack.push(ch1); }else{ //碰到右括号,但栈是空的没有匹配到左括号 if(stack.empty()) { return false; } char ch2 = stack.peek(); if(ch2=='(' && ch1==')' || ch2=='[' && ch1==']'|| ch2=='{' && ch1 == '}') { stack.pop(); }else {//碰到右边括号,但左括号不匹配 return false; } } } //判断字符串遍历完了,但栈没空 return stack.empty(); } }
提交结果：
2. 逆波兰表达式(lc150)
题目描述:
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = [“2”,“1”,“+”,“3”,“*”]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = [“4”,“13”,“5”,“/”,“+”]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = [“10”,“6”,“9”,“3”,“+”,“-11”,““,”/“,””,“17”,“+”,“5”,“+”]
输出：2
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
提示：
1 <= tokens.length <= 104
tokens[i] 是一个算符（“+”、“-”、“*” 或 “/”），或是在范围 [-200, 200] 内的一个整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation
解题思路：
在做这道题之前需要先明白逆波兰表达式是什么, 逆波兰表达式其实就是后缀表达式, 与这个相关的还有前缀和中缀表达式, 至于中缀如何转前缀和后缀这里就不介绍了, 如果需要的话在下面链接中的博客有介绍: 链接
明白中缀和后缀表达式之间的转化后, 这道题其实也不难想, 只需要利用一个栈去实现, 我们可以去创建一个栈, 然后去遍历字符串, 去实现碰到数字就入栈, 碰到是操作符就将栈中两个数字出栈, 然后, 第一个出栈的数字作为右操作数, 第二个出栈的元素作为左操作数, 然后再将计算结果入栈, 循环上述过程, 直至将字符串遍历完, 最终栈中只剩一个元素便是最终的计算结果;
要注意的是是字符串中的数字是数字字符, 再入栈前需要先将数字字符转化为对应的数字再进行入栈.
代码实现：
代码实现： class Solution {
提交结果：
3. 栈的压入、弹出序列(牛客JZ31)
题目描述:
描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。
0<=pushV.length == popV.length <=1000
-1000<=pushV[i]<=1000
pushV 的所有数字均不相同
示例1
输入：[1,2,3,4,5],[4,5,3,2,1]
返回值：true
说明：可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()这样的顺序得到[4,5,3,2,1]这个序列，返回true
示例2
输入：[1,2,3,4,5],[4,3,5,1,2]
返回值：false
说明：由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false
链接：点这里
来源：牛客网
解题思路：
既然这里给出了入栈和出栈的序列, 那么们就可以去模拟这个过程, 我们可以创建一个辅助栈, 然后去对入栈序列进行遍历, 每次遍历将里面的元素入栈, 再去按顺序将出栈序列数组中的元素与栈顶元素比较, 如果相等就出栈, 并比较下一个出栈数组元素与下一次栈顶元素是否相等，相等就出栈, 以此类推直到不相等再进行下一次入栈序列的遍历; 最终遍历结束后, 如果最终栈为空栈，则出栈序列是可能的, 否则就是不可能的。
举例：
入栈1,2,3,4,5
出栈4,5,3,2,1
首先1入辅助栈，此时栈顶1≠4，继续入栈2
此时栈顶2≠4，继续入栈3
此时栈顶3≠4，继续入栈4
此时栈顶4＝4，出栈4，出栈序列向后一位，此时为5，,辅助栈里面是1,2,3
此时栈顶3≠5，继续入栈5
此时栈顶5=5，出栈5,出栈序列向后一位，此时为3，,辅助栈里面是1,2,3
此时栈顶3=3, 出栈3,出栈序列向后一位，此时为2，,辅助栈里面是1,2
此时栈顶2=2, 出栈2,出栈序列向后一位，此时为1，,辅助栈里面是1
此时栈顶1=1, 出栈1,出栈序列向后一位, 此时出栈序列遍历结束, 辅助栈为空栈
代码实现：
import java.util.*; public class Solution { public boolean IsPopOrder(int [] pushA,int [] popA) { Stack<Integer> stack = new Stack(); int j = 0;//用来遍历popA数组 for(int i = 0; i < pushA.length; i++) { stack.push(pushA[i]); while(j<popA.length && !stack.empty() && stack.peek().equals(popA[j])) { stack.pop(); j++; } } return stack.empty(); } }
提交结果：
4.最小栈(lc155)
题目描述:
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
- MinStack() 初始化堆栈对象。
- void push(int val) 将元素val推入堆栈。
- void pop() 删除堆栈顶部的元素。
- int top() 获取堆栈顶部的元素。
- int getMin() 获取堆栈中的最小元素。
示例 1:
输入：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
提示：
-231 <= val <= 231 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/min-stack
解题思路：
这道题的意思是让我们实现一个栈, 要求在时间复杂度为O(1)的情况下获取到最小值;
这里我们可以使用两个栈来实现, 创建一个主站和一个辅助栈, 每次入栈将都将元素入到主栈中, 辅助栈中存放实时的最小值, 那么如何实现在辅助栈中存放实时的最小值? 很简单, 如果是第一次入栈, 那么此时的辅助栈是空栈, 直接将第一个元素在两个栈都入栈, 之后的每次的入栈, 如果待入栈元素的值小于或等于辅助栈的栈顶元素, 那么两个栈都入栈, 否则只入主栈(主栈不论什么情况，均入栈);
代码演示主栈为stack，辅助栈为minStack;
代码实现：
class MinStack { Stack<Integer> stack; Stack<Integer> minStack; public MinStack() { stack = new Stack<>(); minStack = new Stack<>(); } public void push(int val) { stack.push(val); if(minStack.empty()) { minStack.push(val); }else { if(val <= minStack.peek()) { minStack.push(val); } } } public void pop() { if(!stack.empty()) { int x = stack.pop(); if(x == minStack.peek()) { minStack.pop(); } } } public int top() { if(stack.empty()) { return -1; } return stack.peek(); } public int getMin() { if(minStack.empty()) { return -1; } return minStack.peek(); } }
