栈
20. 有效的括号
| 给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 示例 2: 输入: “()[]{}” 输出: true |
|---|
栈顶元素放映了在嵌套的层次关系中，最近的需要匹配的元素
class Solution {public boolean isValid(String s) {if (s.length() % 2 == 0) {Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (c == '{' || c == '[' || c == '(') {stack.push(c);} else if (c == ')') {if (!stack.isEmpty() && stack.peek() == '(')stack.pop();elsereturn false;} else if (c == ']') {if (!stack.isEmpty() && stack.peek() == '[')stack.pop();elsereturn false;} else {if (!stack.isEmpty() && stack.peek() == '{')stack.pop();elsereturn false;}}return stack.isEmpty();}return false;}}
题解思路2：栈+Map映射(避免大量if else 的情况出现)
class Solution {public boolean isValid(String s) {int n = s.length();if (n % 2 != 0) {return false;}Map<Character, Character> map = new HashMap<>();map.put(')', '(');map.put('}', '{');map.put(']', '[');Stack<Character> stack = new Stack<>();for (int i = 0; i < n; i++) {char ch = s.charAt(i);if (map.containsKey(ch)) {if (stack.isEmpty() || stack.peek() != map.get(ch)) {return false;}stack.pop();} else {stack.push(ch);}}return stack.isEmpty();}}
stack.peek( )：查看栈顶元素，但是不出栈 stack.pop( )：弹出栈顶元素 stack.push( )：压入栈中
150. 逆波兰表达式求值
| 根据 逆波兰表示法，求表达式的值。 有效的运算符包括 +, -, , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。 说明：整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。 示例 1： 输入: [“2”, “1”, “+”, “3”, ““] 输出: 9 解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9 |
|---|
题解思路1：通过栈的进栈出栈操作实现
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < tokens.length; i++) {
switch (tokens[i]) {
case "+":
stack.push(stack.pop() + stack.pop());
break;
case "-":
int a = stack.pop();
stack.push(stack.pop() - a);
break;
case "*":
stack.push(stack.pop() * stack.pop());
break;
case "/":
int b = stack.pop();
stack.push(stack.pop() / b);
break;
default:
stack.push(Integer.valueOf(tokens[i]));
break;
}
}
return stack.pop();
}
}
注意减法和除法的顺序问题
题解思路2：纯数组模拟栈的实现
class Solution {
public int evalRPN(String[] tokens) {
int[] numStack = new int[tokens.length / 2 + 1];
int index = 0;
for (String s : tokens) {
switch (s) {
case "+":
numStack[index - 2] += numStack[--index];
break;
case "-":
numStack[index - 2] -= numStack[--index];
break;
case "*":
numStack[index - 2] *= numStack[--index];
break;
case "/":
numStack[index - 2] /= numStack[--index];
break;
default:
numStack[index++] = Integer.parseInt(s);
break;
}
}
return numStack[0];
}
}
Integer.parseInt( ) //减少自动拆箱装箱操作 Integet.valueOd( )
71. 简化路径
| 以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径 请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。 示例 1： 输入：”/home/“ 输出：”/home” 解释：注意，最后一个目录名后面没有斜杠。 |
|---|
题解思路：通过“/”分隔开所有的元素，依次判断进行操作，遇到“.”continue，遇到“..”出栈一个元素，其他情况入栈
public String simplifyPath(String path) {
Stack<String> stack = new Stack<>();
String[] items = path.split("/");
for (String item : items) {
if (item.isEmpty() || item.equals(".")) continue;
if (item.equals("..")) {
if (!stack.empty()) stack.pop();
} else {
stack.push(item);
}
}
return "/" + String.join("/", stack);
}
注意点：判断栈是否为空stack.empty( ) String.join( )的拼接操作
394. 字符串解码
| 给定一个经过编码的字符串，返回它解码后的字符串。 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。示例 1： 输入：s = “3[a]2[bc]” 输出：“aaabcbc” |
|---|
题解思路：难点在于括号内嵌套括号，需要从内向外生成与拼接字符串，这与栈的先入后出的特性对应。
1、构建辅助栈 stack， 遍历字符串 s 中每个字符 c；
- 当 c 为数字时，将数字字符转化为数字 multi，用于后续倍数计算；
- 当 c 为字母时，在 res 尾部添加 c；
- 当 c 为 [ 时，将当前 multi 和 res 入栈，并分别置空置 0：
- 记录此 [ 前的临时结果 res 至栈，用于发现对应 ] 后的拼接操作；
- 记录此 [ 前的倍数 multi 至栈，用于发现对应 ] 后，获取 multi × […] 字符串。
- 进入到新 [ 后，res 和 multi 重新记录。
- 当 c 为 ] 时，stack 出栈，拼接字符串 res = last_res + cur_multi * res，其中:
- last_res是上个 [ 到当前 [ 的字符串，例如 “3[a2[c]]” 中的 a；
- cur_multi是当前 [ 到 ] 内字符串的重复倍数，例如 “3[a2[c]]” 中的 2。
2、返回字符串 res。
class Solution {
public String decodeString(String s) {
StringBuilder res = new StringBuilder();
int multi = 0;
LinkedList<Integer> stack_multi = new LinkedList<>();
LinkedList<String> stack_res = new LinkedList<>();
for (char c : s.toCharArray()) {
if (c >= '0' && c <= '9')
multi = multi * 10 + (c - '0');
else if (c >= 'a' && c <= 'z')
res.append(c);
else if (c == '[') {
stack_multi.addLast(multi);
stack_res.addLast(res.toString());
multi = 0;
res = new StringBuilder();
} else if (c == ']') {
int num = stack_multi.removeLast();
StringBuilder sb = new StringBuilder();
for (int i = 0; i < num; i++) {
sb.append(res);
}
res = new StringBuilder(stack_res.removeLast()).append(sb);
}
}
return res.toString();
}
}
单调栈
注：单调栈有意思的地方就在于栈中存储的元素不是值，而是值的下标索引。
739. 每日温度
请根据每日 气温 列表，重新生成一个列表。对应位置的输出为：要想观测到更高的气温，至少需要等待的天数。如果气温在这之后都不会升高，请在该位置用 0 来代替。例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。提示： 气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。 |
|---|
题解思路1：暴力解
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int len=temperatures.length;
int[] res=new int[len];
for(int i=0;i<len;i++){
res[i]=0;
for(int j=i;j<len;j++){
if(temperatures[j]>temperatures[i]){
res[i]=j-i;
break;
}
}
}
return res;
}
}
题解思路2：单调栈
注：这里栈中存储的数值不是数组中的数值，而是数组中的索引，这是非常关键的一点
class Solution {
public int[] dailyTemperatures(int[] T) {
int length = T.length;
int[] ans = new int[length];
Deque<Integer> stack = new LinkedList<Integer>();
for (int i = 0; i < length; i++) {
int temperature = T[i];
while (!stack.isEmpty() && temperature > T[stack.peek()]) {
int prevIndex = stack.pop();
ans[prevIndex] = i - prevIndex;
}
stack.push(i);
}
return ans;
}
}
84. 柱状图中最大的矩形
| 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。  以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。示例: 输入: [2,1,5,6,2,3] 输出: 10 |
|---|
题解思路1：暴力解法
题解思路：遍历每一个列，将该列的高度作为最大高度，然后向左右分别获取到左右的最大边界
class Solution {
public int largestRectangleArea(int[] heights) {
//这里的暴力题解方式是计算每个列作为高度的情况下可以获得的最大的柱状图的面积
int len = heights.length;
//特例
if (len == 0)
return 0;
int res = 0;
for (int i = 0; i < len; i++) {
//找出左边最后一个大于等于height[i]的下标
int left = i;
int curHeight = heights[i];
while (left > 0 && heights[left-1] >= curHeight) {
left--;
}
//找到右边最后一个大于等于height[i]的下标
int right = i;
while (right < len-1 && heights[right+1] >= curHeight) {
right++;
}
int width = (right - left + 1) * curHeight;
res = Math.max(res, width);
}
return res;
}
}
题解思路2：空间换时间，栈操作
————> 
————> 
————> 
在这个过程中，如何判断哪些列是可以计算作为最大值的预选条件？
1、除了右边要比当前列严格小
2、左边也要比当前高度严格小
class Solution {
public int largestRectangleArea(int[] heights) {
int len=heights.length;
if(len==0)
return 0;
if(len==1)
return heights[0];
int res=0;
Stack<Integer> stack=new Stack<>();
for(int i=0;i<len;i++){
//此处使用while是因为有可能不止一个柱形的最大宽度可以被计算
while(!stack.isEmpty()&&heights[i]<heights[stack.peek()]){
int curHeight=heights[stack.pop()];
//弹出高度相等的元素
while(!stack.isEmpty()&&heights[stack.peek()]==curHeight){
stack.pop();
}
int curwidth;
if(stack.isEmpty()){
curwidth=i;
}else{
curwidth=i-stack.peek()+1;
}
res=Math.max(res,curwidth*curHeight);
}
stack.push(i);
}
//假设遍历完之后还有元素在栈中
while(!stack.isEmpty()){
int curHeight=heights[stack.pop()];
while (!stack.isEmpty() && heights[stack.peek()] == curHeight) {
stack.pop();
}
int curWidth;
if (stack.isEmpty()) {
curWidth = len;
} else {
curWidth = len - stack.peek() - 1;
}
res = Math.max(res, curHeight * curWidth);
}
return res;
}
}
若有收获，就点个赞吧
0 人点赞
