栈
约 7684 字大约 26 分钟
什么是栈?
栈是一种单端线性数据结构，它通过两个主要操作（即推送和弹出）模拟真实世界的栈。
栈是一个先入后出(FILO-First In Last Out)的有序列表。
栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。
使用场景
- 由文本编辑器中的撤消机制使用。
- 用于编译器语法检查以匹配括号和花括号。[(){}]
- 在后台使用以通过跟踪以前的函数调用来支持递归。
- 图的深度优先搜索 (DFS)
- 子程序的调用：在跳往子程序前，会先将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中
- 处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中。
- 表达式的转换
[中缀表达式转后缀表达式]与求值(实际解决)。 - 二叉树的遍历。
- 汉诺塔
- 问题:表达式2x7x1+5计算机底层怎么计算,计算机收到的是一个字符串
复杂度分析
pushing O(1)
popping O(1)
peeking O(1)
searching O(n)因为可能要搜索整个链表
size O(1)
单调栈是一种特殊的栈，它的特点是栈内的元素保持某种单调性。根据单调性的不同，可以分为单调递增栈和单调递减栈。单调递增栈
- 定义: 单调递增栈中的元素从栈底到栈顶是严格递增的（即：栈顶元素小于或等于栈底元素）。
- 维护规则:当新元素要入栈时，如果栈顶元素大于或等于新元素，则弹出栈顶元素，直到栈顶元素小于新元素或栈为空时，再将新元素入栈。
- 作用:栈顶找到右边第一个比他小的元素
- 应用场景: 典型的应用是在解决“柱状图中最大的矩形面积”问题时，利用单调递增栈来确定每个柱子的左、右边界。
单调递减栈
- 定义: 单调递减栈中的元素从栈底到栈顶是严格递减的（即：栈顶元素大于或等于栈底元素）。
- 维护规则:当新元素要入栈时，如果栈顶元素小于或等于新元素，则弹出栈顶元素，直到栈顶元素大于新元素或栈为空时，再将新元素入栈。
- 作用:栈顶找到右边第一个比他大的元素
- 应用场景: 单调递减栈常用于寻找“下一个更大元素”的问题，例如在股票价格、温度变化等场景中。
区别与选择
单调递增栈:主要用于寻找数组中比当前元素小的值或寻找最小值问题。可以帮助在 O(n) 的时间复杂度内找到某个元素的左右边界。
通常用于“最小值”问题，比如找到某个柱子左右最近的高度小于等于它的柱子。
单调递减栈:主要用于寻找数组中比当前元素大的值或寻找最大值问题。
常用于解决“最大值”问题，比如找到每个元素在其右边第一个大于它的元素。
在股票买卖问题或温度问题中，它可以有效地找到某一天之后的最高温度或最高股票价格。
基于数组实现stack
public class ArrayStack<E> implements Stack<E>, Iterable<E>{
private final E[] array;
private int top = 0;
@SuppressWarnings("all")
public ArrayStack(int capacity) {
this.array = (E[]) new Object[capacity];
}
@Override
public boolean push(E value) {
if (isFull()) {
return false;
}
array[top++] = value;
return true;
}
@Override
public E pop() {
if (isEmpty()) {
return null;
}
return array[--top];
}
@Override
public E peek() {
if (isEmpty()) {
return null;
}
return array[top-1];
}
@Override
public boolean isEmpty() {
return top == 0;
}
@Override
public boolean isFull() {
return top == array.length;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
int p = top;
@Override
public boolean hasNext() {
return p > 0;
}
@Override
public E next() {
return array[--p];
}
};
}
}
基于链表实现stack
public class LinkedListStack<E> implements Stack<E>, Iterable<E> {
private final int capacity;
private int size;
private final Node<E> head = new Node<>(null, null);
public LinkedListStack(int capacity) {
this.capacity = capacity;
}
@Override
public boolean push(E value) {
if (isFull()) {
return false;
}
head.next = new Node<>(value, head.next);
size++;
return true;
}
@Override
public E pop() {
if (isEmpty()) {
return null;
}
Node<E> first = head.next;
head.next = first.next;
size--;
return first.value;
}
@Override
public E peek() {
if (isEmpty()) {
return null;
}
return head.next.value;
}
@Override
public boolean isEmpty() {
return head.next == null;
}
@Override
public boolean isFull() {
return size == capacity;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
Node<E> p = head.next;
@Override
public boolean hasNext() {
return p != null;
}
@Override
public E next() {
E value = p.value;
p = p.next;
return value;
}
};
}
static class Node<E> {
E value;
Node<E> next;
public Node(E value, Node<E> next) {
this.value = value;
this.next = next;
}
}
}
前缀表达式
- 从右至左扫描表达式，遇到数字时压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素和次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
- 例如:
(3+4)×5-6对应的前缀表达式就是- × + 3 4 5 6, 针对前缀表达式求值步骤如下:- 从右至左扫描，将6、5、4、3压入堆栈
- 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈
- 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
- 最后是-运算符，计算出35-6的值，即29，由此得出最终结果
中缀表达式(波兰表达式)
- 中缀表达式如
(3+4)×5-6，对计算机来说却不好操作，因此，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式.) - 使用栈完成(中缀)表达式的计算思路
- 通过一个index值（索引），来遍历我们的表达式
- 如果我们发现是一个数字, 就直接入数栈
- 如果发现扫描到是一个符号, 就分如下情况
- 如果发现当前的符号栈为空，就直接入栈
- 如果符号栈有操作符，就进行比较,
- 如果当前的操作符的优先级小于或者等于栈中的操作符，就需要从数栈中pop出两个数,在从符号栈中pop出一个符号，进行运算，将得到结果入数栈，然后将当前的操作符入符号栈，
- 如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.
- 当表达式扫描完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行.
- 最后在数栈只有一个数字，就是表达式的结果
在上个例子中添加三个方法，并改名为ArrayStack2类
返回运算符的优先级 数字越大，则优先级就越高
public int priority(int oper) {
if(oper == '*' || oper == '/'){
return 1;
} else if (oper == '+' || oper == '-') {
return 0;
} else {
return -1; // 假定目前的表达式只有 +, - , * , /
}
}
//判断是不是一个运算符
public boolean isOper(char val) {
return val == '+' || val == '-' || val == '*' || val == '/';
}
//计算方法
public int cal(int num1, int num2, int oper) {
int res = 0; // res 用于存放计算的结果
switch (oper) {
case '+':
res = num1 + num2;
break;
case '-':
res = num2 - num1;// 注意顺序
break;
case '*':
res = num1 * num2;
break;
case '/':
res = num2 / num1;
break;
default:
break;
}
return res;
}
计算器实现
public class Calculator {
public static void main(String[] args) {
String expression = "7*2*2-5+1-5+3-4"; // 15//如何处理多位数的问题？
ArrayStack2 numStack = new ArrayStack2(10);//创建两个栈，数栈，一个符号栈
ArrayStack2 operStack = new ArrayStack2(10);
int index = 0;//用于扫描//定义需要的相关变量
int num1 = 0;
int num2 = 0;
int oper = 0;
int res = 0;
char ch = ' '; //将每次扫描得到char保存到ch
String keepNum = ""; //用于拼接 多位数
while(true) {//开始while循环的扫描expression
ch = expression.substring(index, index+1).charAt(0);//依次得到expression 的每一个字符
//判断ch是什么，然后做相应的处理
if(operStack.isOper(ch)) {//如果是运算符
if(!operStack.isEmpty()) {//判断当前的符号栈是否为空
//如果符号栈有操作符，就进行比较,如果当前的操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop出两个数,
//在从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈
if(operStack.priority(ch) <= operStack.priority(operStack.peek())) {
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
numStack.push(res);//把运算的结果如数栈
operStack.push(ch);//然后将当前的操作符入符号栈
} else {//如果当前的操作符的优先级大于栈中的操作符， 就直接入符号栈.
operStack.push(ch);
}
}else {
operStack.push(ch); // 1 + 3//如果为空直接入符号栈..
}
} else { //如果是数，则直接入数栈
//numStack.push(ch - 48); //? "1+3" '1' => 1
//1. 当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
//2. 在处理数，需要向expression的表达式的index 后再看一位,如果是数就进行扫描，如果是符号才入栈
//3. 因此我们需要定义一个变量 字符串，用于拼接
keepNum += ch;//处理多位数
//如果ch已经是expression的最后一位，就直接入栈
if (index == expression.length() - 1) {
numStack.push(Integer.parseInt(keepNum));
}else{
//判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈
//注意是看后一位，不是index++
if (operStack.isOper(expression.substring(index+1,index+2).charAt(0))) {
numStack.push(Integer.parseInt(keepNum));//如果后一位是运算符，则入栈 keepNum = "1" 或者 "123"
keepNum = ""; //重要的!!!!!!, keepNum清空
}
}
}
index++;//让index + 1, 并判断是否扫描到expression最后.
if (index >= expression.length()) break;
}
while(true) {//当表达式扫描完毕，就顺序的从 数栈和符号栈中pop出相应的数和符号，并运行.
//如果符号栈为空，则计算到最后的结果, 数栈中只有一个数字【结果】
if(operStack.isEmpty()break;
num1 = numStack.pop();
num2 = numStack.pop();
oper = operStack.pop();
res = numStack.cal(num1, num2, oper);
numStack.push(res);//入栈
}
int res2 = numStack.pop();//将数栈的最后数，pop出，就是结果
System.out.printf("表达式 %s = %d", expression, res2);
}
}
后缀表达式(逆波兰表达式)
- 与前缀表达式相似，只是运算符位于操作数之后
- 后缀表达式计算:
- 举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –
- 从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果
- 例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:
- 从左至右扫描，将3和4压入堆栈；遇到+运算符，弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；将5入栈；
- 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；将6入栈；最后是-运算符，计算出35-6的值，即29，由此得出最终结果
逆波兰表达式计算实现
public class PolandNotation {
public static void main(String[] args) {
//(30+4)×5-6 => 30 4 + 5 × 6 - => 164 先定义给逆波兰表达式
//为了方便，逆波兰表达式 的数字和符号使用空格隔开
//String suffixExpression = "30 4 + 5 * 6 -";
//1. 先将 "30 4 + 5 × 6 - " => 放到ArrayList中,上面是扫描字符串，改成ArrayList方便一点
//2. 将 ArrayList 传递给一个方法，遍历 ArrayList 配合栈 完成计算
List<String> list = getListString(suffixExpression);
System.out.println("rpnList=" + list);
int res = calculate(list);
System.out.println("计算的结果是=" + res);
}
//将一个逆波兰表达式， 依次将数据和运算符 放入到 ArrayList中
public static List<String> getListString(String suffixExpression) {
//将 suffixExpression 分割
String[] split = suffixExpression.split(" ");
List<String> list = new ArrayList<String>();
for(String ele: split) {
list.add(ele);
}
return list;
}
//完成对逆波兰表达式的运算
public static int calculate(List<String> ls) {
Stack<String> stack = new Stack<String>();// 创建给栈, 只需要一个栈即可
for (String item : ls) {// 遍历 ls
if (item.matches("\\d+")) { // 使用正则表达式来取出数 匹配的是多位数
stack.push(item);
} else {
int num2 = Integer.parseInt(stack.pop());// pop出两个数，并运算， 再入栈
int num1 = Integer.parseInt(stack.pop());
int res = 0;
if (item.equals("+")) {
res = num1 + num2;
} else if (item.equals("-")) {
res = num1 - num2;
} else if (item.equals("*")) {
res = num1 * num2;
} else if (item.equals("/")) {
res = num1 / num2;
} else {
throw new RuntimeException("运算符有误");
}
stack.push("" + res); //把res 入栈
}
}
return Integer.parseInt(stack.pop());//最后留在stack中的数据是运算结果
}
}
- 中缀表达式转成后缀表达式
- 1) 初始化两个栈：运算符栈s1和储存中间结果的栈s2；
- 2) 从左至右扫描中缀表达式；
- 3) 遇到操作数时，将其压s2；
- 4) 遇到运算符时，比较其与s1栈顶运算符的优先级：
- 1.如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；
- 2.否则，若优先级比栈顶运算符的高，也将运算符压入s1；
- 3.否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较；
- 5) 遇到括号时：
- (1) 如果是左括号“(”，则直接压入s1
- (2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
- 6) 重复步骤2至5，直到表达式的最右边
- 7) 将s1中剩余的运算符依次弹出并压入s2
- 8) 依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
public class PolandNotation {
public static void main(String[] args) {
//完成将一个中缀表达式转成后缀表达式的功能
//1. 1+((2+3)×4)-5 => 转成 1 2 3 + 4 × + 5 –
//2. 因为直接对str 进行操作，不方便，因此 先将 "1+((2+3)×4)-5" =》 中缀的表达式对应的List
// 即 "1+((2+3)×4)-5" => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
//3. 将得到的中缀表达式对应的List => 后缀表达式对应的List
// 即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]
String expression = "1+((2+3)*4)-5";//注意表达式
List<String> infixExpressionList = toInfixExpressionList(expression);
System.out.println("中缀表达式对应的List=" + infixExpressionList); // ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
List<String> suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);
System.out.println("后缀表达式对应的List" + suffixExpreesionList); //ArrayList [1,2,3,+,4,*,+,5,–]
System.out.printf("expression=%d", calculate(suffixExpreesionList)); // ?//计算取上面那个
}
//即 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] =》 ArrayList [1,2,3,+,4,*,+,5,–]
//方法：根据中缀表达式对应的List => 后缀表达式对应的List
public static List<String> parseSuffixExpreesionList(List<String> ls) {
//定义两个栈
Stack<String> s1 = new Stack<String>(); // 符号栈
//因为s2 这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
//因此比较麻烦，这里我们就不用 Stack<String> 直接使用 List<String> s2
//Stack<String> s2 = new Stack<String>(); // 储存中间结果的栈s2
List<String> s2 = new ArrayList<String>(); // 储存中间结果的Lists2
for(String item: ls) {
if(item.matches("\\d+")) {//如果是一个数，加入s2
s2.add(item);
} else if (item.equals("(")) {
s1.push(item);
} else if (item.equals(")")) {
while(!s1.peek().equals("(")) {//如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
s2.add(s1.pop());
}
s1.pop();//!!! 将 ( 弹出 s1栈， 消除小括号
} else {
//当item的优先级小于等于s1栈顶运算符, 将s1栈顶的运算符弹出并加入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较
while(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item) ) {
s2.add(s1.pop());
}
s1.push(item);//还需要将item压入栈
}
}
while(s1.size() != 0) {//将s1中剩余的运算符依次弹出并加入s2
s2.add(s1.pop());
}
return s2; //注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List
}
//方法：将中缀表达式转成对应的List s="1+((2+3)×4)-5";
public static List<String> toInfixExpressionList(String s) {
//定义一个List,存放中缀表达式 对应的内容
List<String> ls = new ArrayList<String>();
int i = 0; //这时是一个指针，用于遍历 中缀表达式字符串
String str; // 对多位数的拼接
char c; // 每遍历到一个字符，就放入到c
do {
if((c=s.charAt(i)) < 48 || (c=s.charAt(i)) > 57) {//如果c是一个非数字，我需要加入到ls
ls.add("" + c);
i++; //i需要后移
} else { //如果是一个数，需要考虑多位数
str = ""; //先将str 置成"" '0'[48]->'9'[57]
while(i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57) {
str += c;//拼接
i++;
}
ls.add(str);
}
}while(i < s.length());
return ls;//返回
}
}
//编写一个类 Operation 可以返回一个运算符 对应的优先级
class Operation {
private static int ADD = 1;
private static int SUB = 1;
private static int MUL = 2;
private static int DIV = 2;
//写一个方法，返回对应的优先级数字
public static int getValue(String operation) {
int result = 0;
switch (operation) {
case "+":
result = ADD;
break;
case "-":
result = SUB;
break;
case "*":
result = MUL;
break;
case "/":
result = DIV;
break;
default:
System.out.println("不存在该运算符" + operation);
break;
}
return result;
}
}
- 逆波兰表达式完整版
支持 + - * / ( )
多位数，支持小数,
兼容处理, 过滤任何空白字符，包括空格、制表符、换页符
public class ReversePolishMultiCalc {
static final String SYMBOL = "\\+|-|\\*|/|\\(|\\)";//匹配 + - * / ( ) 运算符
static final String LEFT = "(",RIGHT = ")",ADD = "+",MINUS= "-",TIMES = "*",DIVISION = "/";
static final int LEVEL_01 = 1,LEVEL_02 = 2,LEVEL_HIGH = Integer.MAX_VALUE;//1+-,2*/,3()
static Stack<String> stack = new Stack<>();
static List<String> data = Collections.synchronizedList(new ArrayList<String>());
//去除所有空白符
public static String replaceAllBlank(String s ){
return s.replaceAll("\\s+","");// \\s+ 匹配任何空白字符，包括空格、制表符、换页符等等, 等价于[ \f\n\r\t\v]
}
//判断是不是数字 int double long float
public static boolean isNumber(String s){
Pattern pattern = Pattern.compile("^[-\\+]?[.\\d]*$");
return pattern.matcher(s).matches();
}
//判断是不是运算符
public static boolean isSymbol(String s){
return s.matches(SYMBOL);
}
//匹配运算等级
public static int calcLevel(String s){
if("+".equals(s) || "-".equals(s)){
return LEVEL_01;
} else if("*".equals(s) || "/".equals(s)){
return LEVEL_02;
}
return LEVEL_HIGH;
}
//匹配
public static List<String> doMatch (String s) throws Exception{
if(s == null || "".equals(s.trim())) throw new RuntimeException("data is empty");
if(!isNumber(s.charAt(0)+"")) throw new RuntimeException("data illeagle,start not with a number");
s = replaceAllBlank(s);//去掉所有空白
String each;
int start = 0;
for (int i = 0; i < s.length(); i++) {
if(isSymbol(s.charAt(i)+"")){
each = s.charAt(i)+"";
//栈为空，(操作符，或者 操作符优先级大于栈顶优先级 && 操作符优先级不是"("和")"的优先级 （ ")" 不能直接入栈）
if(stack.isEmpty() || LEFT.equals(each)
|| ((calcLevel(each) > calcLevel(stack.peek())) && calcLevel(each) < LEVEL_HIGH)){
stack.push(each);
}else if( !stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())){
//栈非空，操作符优先级小于等于栈顶优先级时出栈入列，直到栈为空，或者遇到了(，最后操作符入栈
while (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek()) ){
if(calcLevel(stack.peek()) == LEVEL_HIGH){
break;
}
data.add(stack.pop());
}
stack.push(each);
}else if(RIGHT.equals(each)){
// ) 操作符，依次出栈入列直到空栈或者遇到了第一个)操作符，此时)出栈
while (!stack.isEmpty() && LEVEL_HIGH >= calcLevel(stack.peek())){
if(LEVEL_HIGH == calcLevel(stack.peek())){
stack.pop();
break;
}
data.add(stack.pop());//去掉"("
}
}
start = i ; //前一个运算符的位置
}else if( i == s.length()-1 || isSymbol(s.charAt(i+1)+"") ){
each = start == 0 ? s.substring(start,i+1) : s.substring(start+1,i+1);
if(isNumber(each)) {
data.add(each);
continue;
}
throw new RuntimeException("data not match number");
}
}
//如果栈里还有元素，此时元素需要依次出栈入列，可以想象栈里剩下栈顶为/，栈底为+，应该依次出栈入列，可以直接翻转整个stack 添加到队列
Collections.reverse(stack);
data.addAll(new ArrayList<>(stack));
return data;
}
//算出结果
public static Double doCalc(List<String> list){
Double d = 0d;
if(list == null || list.isEmpty())return null;
if (list.size() == 1) return Double.valueOf(list.get(0));//只剩一个数
ArrayList<String> list1 = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
list1.add(list.get(i));
if(isSymbol(list.get(i))){
Double d1 = doTheMath(list.get(i - 2), list.get(i - 1), list.get(i));
list1.remove(i);
list1.remove(i-1);
list1.set(i-2,d1+"");
list1.addAll(list.subList(i+1,list.size()));
break;
}
}
doCalc(list1);
return d;
}
//运算
public static Double doTheMath(String s1,String s2,String symbol){
Double result ;
switch (symbol){
case ADD : result = Double.valueOf(s1) + Double.valueOf(s2); break;
case MINUS : result = Double.valueOf(s1) - Double.valueOf(s2); break;
case TIMES : result = Double.valueOf(s1) * Double.valueOf(s2); break;
case DIVISION : result = Double.valueOf(s1) / Double.valueOf(s2); break;
default : result = null;
}
return result;
}
public static void main(String[] args) {
//String math = "9+(3-1)*3+10/2";
String math = "12.8 + (2 - 3.55)*4+10/5.0";
try {
doCalc(doMatch(math));
} catch (Exception e) {
e.printStackTrace();
}
}
}
t20有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
时间复杂度：O(n)，其中 n 是字符串 s 的长度。
空间复杂度：O(n+∣Σ∣)，其中 Σ 表示字符集，
本题中字符串只包含 6 种括号，∣Σ∣=6。栈中的字符数量为 O(n)，
而哈希表使用的空间为 O(∣Σ∣)，相加即可得到总空间复杂度。
public boolean isValid(String s) {
int n = s.length();
if (n % 2 == 1) {
return false;
}
Map<Character, Character> pairs = new HashMap<Character, Character>() {{
put(')', '(');
put(']', '[');
put('}', '{');
}};
Deque<Character> stack = new LinkedList<Character>();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (pairs.containsKey(ch)) {
if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
return false;
}
stack.pop();
} else {
stack.push(ch);
}
}
return stack.isEmpty();
}
t155最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
时间复杂度O(1)。因为栈的插入、删除与读取操作都是 O(1)，我们定义的每个操作最多调用栈操作两次。
空间复杂度O(n)，其中 n 为总操作数。最坏情况下连续插入n个元素，此时两个栈占用的空间为 O(n)。
class MinStack {
Deque<Integer> xStack;
Deque<Integer> minStack;
public MinStack() {
xStack = new LinkedList<Integer>();
minStack = new LinkedList<Integer>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int x) {
xStack.push(x);
minStack.push(Math.min(minStack.peek(), x));
}
public void pop() {
xStack.pop();
minStack.pop();
}
public int top() {
return xStack.peek();
}
public int getMin() {
return minStack.peek();
}
}
t394字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：输入：s = "3[a]2[bc]" 输出："aaabcbc"
3[a2[c]] ==>accaccacc
时间复杂度：记解码后得出的字符串长度为 S，
遍历一次原字符串 s，和将解码后的字符串中的每个字符都入栈，
并最终拼接进答案中，故时间复杂度为 O(S+∣s∣)，即 O(S)。
空间复杂度：记解码后得出的字符串长度为 S，这里用栈维护 TOKEN，
栈的总大小最终与 S 相同，故渐进空间复杂度为 O(S)
class Solution {
int ptr;
public String decodeString(String s) {
LinkedList<String> stk = new LinkedList<String>();
ptr = 0;
while (ptr < s.length()) {
char cur = s.charAt(ptr);
if (Character.isDigit(cur)) {
// 获取一个数字并进栈
String digits = getDigits(s);
stk.addLast(digits);
} else if (Character.isLetter(cur) || cur == '[') {
// 获取一个字母并进栈
stk.addLast(String.valueOf(s.charAt(ptr++)));
} else {
//把栈顶的数字和[中的字母拿出来组成字符串后加回去栈顶
++ptr;//跳过']'
LinkedList<String> sub = new LinkedList<String>();
while (!"[".equals(stk.peekLast())) {
sub.addLast(stk.removeLast());
}
//翻转：因为压栈时再加到list中是相反的
Collections.reverse(sub);
// 左括号出栈
stk.removeLast();
// 此时栈顶为当前 sub 对应的字符串应该出现的次数
int repTime = Integer.parseInt(stk.removeLast());
StringBuffer t = new StringBuffer();
String o = getString(sub);
// 构造字符串
while (repTime-- > 0) {
t.append(o);
}
// 将构造好的字符串入栈
stk.addLast(t.toString());
}
}
return getString(stk);
}
public String getDigits(String s) {
StringBuffer ret = new StringBuffer();
while (Character.isDigit(s.charAt(ptr))) {
ret.append(s.charAt(ptr++));
}
return ret.toString();
}
public String getString(LinkedList<String> v) {
StringBuffer ret = new StringBuffer();
for (String s : v) {
ret.append(s);
}
return ret.toString();
}
}
t739每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:输入: temperatures = [73,74,75,71,69,72,76,73]输出: [1,1,4,2,1,1,0,0]
示例 2:输入: temperatures = [30,40,50,60]输出: [1,1,1,0]
时间复杂度：O(n)，n是温度列表的长度。
正向遍历温度列表一遍，对于温度列表中的每个下标，最多有一次进栈和出栈的操作。
空间复杂度：O(n)，n是温度列表的长度。
需要维护一个单调栈存储温度列表中的下标。
思路：使用单调递减栈找出左边第一个
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int length = temperatures.length;
int[] ans = new int[length];
Deque<Integer> stack = new LinkedList<Integer>();
//单调递减栈，栈顶找到第一个右边比他大的数
for (int i = 0; i < length; i++) {
int temperature = temperatures[i];
while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
int prevIndex = stack.pop();
ans[prevIndex] = i - prevIndex;//当前i到大于栈里面元素的距离
}
stack.push(i);//单调递减
}
return ans;
}
}
t84柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
时间复杂度：O(N)。
空间复杂度：O(N)。
思路：计算每一根柱子左右两边第一个小于当前高度的柱子组成的面积的最大值
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int[] left = new int[n];
int[] right = new int[n];
//单调递增栈，栈顶找到右边第一个比它小的数
Deque<Integer> mono_stack = new ArrayDeque<Integer>();
for (int i = 0; i < n; ++i) {
while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
mono_stack.pop();
}
left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
mono_stack.push(i);
}
//单调递增栈，栈顶找到左边第一个比它小的数
mono_stack.clear();
for (int i = n - 1; i >= 0; --i) {
while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
mono_stack.pop();
}
right[i] = (mono_stack.isEmpty() ? n : mono_stack.peek());
mono_stack.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
}
return ans;
}
}
1047删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：输入："abbaca" 输出："ca"
解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
class Solution {
public String removeDuplicates(String S) {
//ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
//https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
ArrayDeque<Character> deque = new ArrayDeque<>();
char ch;
for (int i = 0; i < S.length(); i++) {
ch = S.charAt(i);
if (deque.isEmpty() || deque.peek() != ch) {
deque.push(ch);
} else {
deque.pop();
}
}
String str = "";
//剩余的元素即为不重复的元素
while (!deque.isEmpty()) {
str = deque.pop() + str;
}
return str;
}
}
496下一个更大元素 I
给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
示例 1:输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
示例 2: 输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出-1 。
思路：使用单调递减栈，通过hashMap判断弹出时是否需要记录结果得到子集每个元素的第一个比它大的数字
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Stack<Integer> temp = new Stack<>();
int[] res = new int[nums1.length];
Arrays.fill(res,-1);
//建立nums1的key-value
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0 ; i< nums1.length ; i++){
hashMap.put(nums1[i],i);
}
temp.add(0);
//单调递减栈，给栈顶找到第一个比他大的数值
for (int i = 1; i < nums2.length; i++) {
if (nums2[i] <= nums2[temp.peek()]) {
temp.add(i);
} else {
while (!temp.isEmpty() && nums2[temp.peek()] < nums2[i]) {
if (hashMap.containsKey(nums2[temp.peek()])){
Integer index = hashMap.get(nums2[temp.peek()]);
res[index] = nums2[i];
}
temp.pop();
}
temp.add(i);
}
}
return res;
}
}
503下一个更大元素II
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例 1:输入: [1,2,1] 输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；数字 2 找不到下一个更大的数；第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
思路：使用单调递减栈找到栈顶的下一个比他大的数只不过索引是i%size
class Solution {
public int[] nextGreaterElements(int[] nums) {
//边界判断
if(nums == null || nums.length <= 1) {
return new int[]{-1};
}
int size = nums.length;
int[] result = new int[size];//存放结果
Arrays.fill(result,-1);//默认全部初始化为-1
Stack<Integer> st= new Stack<>();//栈中存放的是nums中的元素下标
for(int i = 0; i < 2*size; i++) {
while(!st.empty() && nums[i % size] > nums[st.peek()]) {
result[st.peek()] = nums[i % size];//更新result
st.pop();//弹出栈顶
}
st.push(i % size);
}
return result;
}
}