面试经典150题——栈

---

1、有效的括号

1.1 题目链接

点击跳转到题目位置

1.2 题目描述

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。

1.3 解题代码

class Solution {public boolean isValid(String s) {int n = s.length();if((n & 1) > 0){return false;}Stack<Character> stk = new Stack<>();for(int i = 0; i < n; ++i){char ch = s.charAt(i);if(stk.isEmpty()){stk.push(ch);continue;}char ch1 = stk.peek();if(ch == ')' && ch1 == '(' || ch == ']' && ch1 == '[' || ch == '}' && ch1 == '{'){stk.pop();} else if(ch == '(' || ch == '[' || ch == '{'){stk.push(ch);} else{return false;}}return stk.isEmpty();}
}

1.4 解题思路

1. 栈的经典题目括号匹配问题。
2. 如果栈为空则将括号压入数组中，如果栈顶元素和当前元素括号匹配，则出栈，否则入栈。
3. 最后遍历完毕若栈为空则返回false，否则返回true。

2、

2.1 题目链接

点击跳转到题目位置

2.2 题目描述

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/’ 开头），请你将其转化为 更加简洁的规范路径。

在 Unix 风格的文件系统中规则如下：

• 一个点 ‘.’ 表示当前目录本身。
• 此外，两个点 ‘…’ 表示将目录切换到上一级（指向父目录）。
• 任意多个连续的斜杠（即，‘//’ 或 ‘///’）都被视为单个斜杠 ‘/’。
• 任何其他格式的点（例如，‘…’ 或 ‘…’）均被视为有效的文件/目录名称。

返回的 简化路径 必须遵循下述格式：

• 始终以斜杠 ‘/’ 开头。
• 两个目录名之间必须只有一个斜杠 ‘/’ 。
• 最后一个目录名（如果存在）不能 以 ‘/’ 结尾。
• 此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘…’）。

返回简化后得到的 规范路径 。

提示：

• 1 <= path.length <= 3000
• path 由英文字母，数字，‘.’，‘/’ 或 ‘_’ 组成。
• path 是一个有效的 Unix 风格绝对路径。

2.3 解题代码

class Solution {public String simplifyPath(String path) {StringBuffer ret = new StringBuffer();Stack<String> stk = new Stack<>();StringBuffer sb = new StringBuffer();for(int i = 0; i < path.length(); ++i){if(path.charAt(i) == '/'){if(sb.length() != 0){stk.push(sb.toString());}sb.delete(0, sb.length());} else{sb.append(path.charAt(i));}}if(sb.length() > 0){stk.push(sb.toString());}List<String> temp = new ArrayList<String>();while(!stk.empty()){if(stk.peek().equals(".")){stk.pop();} else if(stk.peek().equals("..")){stk.pop();int num = 1;while(!stk.empty() && num > 0){if(stk.peek().equals(".")){stk.pop();continue;} else if(stk.peek().equals("..")){stk.pop();num++;} else{stk.pop();num--;}}} else{temp.add(stk.peek());stk.pop();}}int n = temp.size();for(int i = n - 1; i >= 0; --i){ret.append("/");ret.append(temp.get(i));}if(n == 0){ret.append("/");}return ret.toString();}
}

2.4 解题思路

1. 先用字符串数组存储所有的字符串（以一个或多个‘/’分隔）。
2. 接着用栈来去除掉所有多余的字符串，‘.’去除栈顶一个，‘…’去除栈顶两个，如果去除的有‘…’则需要再多去除一个。其他非上述的字符串则放入字符串数组中。
3. 最后再逆序遍历该字符串数组，按照正确的格式拼接成一个字符串返回。

3、最小栈

3.1 题目链接

点击跳转到题目位置

3.2 题目描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

提示：

• -2³¹ <= val <= 2³¹ - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 3 * 10⁴ 次

3.3 解题代码

class MinStack {Stack<Integer> Min = new Stack<>();Stack<Integer> stk = new Stack<>();public MinStack() {while(!Min.empty()){Min.pop();}while(!stk.empty()){stk.pop();}}public void push(int val) {stk.push(val);if(Min.empty()){Min.push(val);} else{if(val < Min.peek()){Min.push(val);} else{Min.push(Min.peek());}}}public void pop() {stk.pop();Min.pop();}public int top() {return stk.peek();}public int getMin() {return Min.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.4 解题思路

1. 用一个栈正常进入入栈出栈操作。
2. 维护一个最小栈，当栈顶为空的时候正常入栈，如果栈顶非空，如果当前栈中元素大于该元素则入最小栈，否则的话则将最小栈顶元素继续入栈。

4、逆波兰表达式求值

4.1 题目链接

点击跳转到题目位置

4.2 题目描述

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

• 有效的算符为 ‘+’、‘-’、‘*’ 和 ‘/’ 。
• 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
• 两个整数之间的除法总是 向零截断 。
• 表达式中不含除零运算。
• 输入是一个根据逆波兰表示法表示的算术表达式。
• 答案及所有中间计算结果可以用 32 位 整数表示。

提示：

1 <= tokens.length <= 104
tokens[i] 是一个算符（“+”、“-”、“*” 或 “/”），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

• 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
• 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。

• 适合用栈操作运算：遇到数字则入栈；
• 遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

4.3 解题代码

class Solution {int Alter(String s){int num = 0;if(s.charAt(0) >= '0' && s.charAt(0) <= '9'){for(int i = 0; i < s.length(); ++i){num *= 10;num += s.charAt(i) - '0';}} else{for(int i = 1; i < s.length(); ++i){num *= 10;num += s.charAt(i) - '0';}num *= -1;}return num;}int calculate(char ch, int num1, int num2){if(ch == '+'){return num2 + num1;} else if(ch == '-'){return num2 - num1;} else if(ch == '*'){return num2 * num1;} else if(ch == '/'){return num2 / num1;}return -1;}public int evalRPN(String[] tokens) {Stack<Integer> stk = new Stack<>();int n = tokens.length;for(int i = 0; i < n; ++i){String str = tokens[i];if(!str.equals("+") && !str.equals("-") && !str.equals("*") && !str.equals("/")){stk.push(Alter(str));} else{int num1 = stk.peek();stk.pop();int num2 = stk.peek();stk.pop();stk.push(calculate(str.charAt(0), num1, num2));}}return stk.peek();}
}

4.4 解题思路

1. 用栈直接模拟逆波兰表达式的过程即可。

5、基本计算器

5.1 题目链接

点击跳转到题目位置

5.2 题目描述

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

提示：

• 1 <= s.length <= 3 * 10⁵
• s 由数字、‘+’、‘-’、‘(’、‘)’、和 ’ ’ 组成
• s 表示一个有效的表达式
• ‘+’ 不能用作一元运算(例如， “+1” 和 “+(2 + 3)” 无效)
• ‘-’ 可以用作一元运算(即 “-1” 和 “-(2 + 3)” 是有效的)
• 输入中不存在两个连续的操作符
• 每个数字和运行的计算将适合于一个有符号的 32位 整数

5.3 解题代码

class Solution {public int calculate(String s) {int sum = 0;int i = 0;int n = s.length();Stack<Integer> stk = new Stack<>();int sign = 1;stk.push(1); // 一开始默认是加号while(i < n){char ch = s.charAt(i);if(ch == ' '){++i;} else if(ch == '+'){sign = stk.peek();      ++i;} else if(ch == '-'){sign = (stk.peek() * -1);++i;} else if(ch == '('){stk.push(sign);++i;} else if(ch == ')'){stk.pop();++i;} else{int num = 0;while(i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9'){num *= 10;num += s.charAt(i) - '0';++i;}sum += sign * num;}            }return sum;}
}

5.4 解题思路

1. 首先往栈顶放入数字1，表示加号。
2. 如果碰到‘+’则符号位设置为栈顶元素，如果碰到‘-’则符号位设置为栈顶元素 * -1，如果遇到左括号，则当前符号为负，则往栈顶元素放入-1，反之则为1，即当前存储的符号位。
3. 从左往后每次遇到数字则结果加上符号位 * 数字即可。