03数据结构与算法刷题之【栈】篇

前言

除了去年11月份以及今年近几月的算法刷题之外，只有在当时20年蓝桥杯准备的时候才刷过一些题，在当时就有接触到一些动归、递归回溯、贪心等等，不过那会也还是一知半解，做的题目也特别少，因为考虑到之后面试有算法题以及数据结构算法对于一个程序员十分重要，我也开始了刷题之路。

我目前的学习数据结构与算法及刷题路径：

1、学习数据结构的原理以及一些常见算法。

2、代码随想录：跟着这个github算法刷题项目进行分类刷，在刷题前可以学习一下对应类别的知识点，而且这里面每道题都讲的很详细。

3、牛客网高频面试101题：牛客网—面试必刷101题，在刷的过程中可以在leetcode同步刷一下。

4、接下来就是力扣上的专栏《剑指offer II》、《程序员面试金典（第 6 版）》…有对应的精选题单来对着刷即可。

5、大部分的高频面试、算法题刷完后，就可以指定力扣分类专栏进行一下刷题了。

刚开始刷的时候真的是很痛苦的，想到去年一道题可能就需要好几小时，真的就很难受的，不过熬过来一切都会好起来，随着题量的增多，很多题目你看到就会知道使用什么数据结构或者算法来去求解，并且思考对应的时间空间复杂度，并寻求最优解，我们一起加油！

我的刷题历程

截止2022.8.18：

1、牛客网101题(其中1题是平台案例有问题)：

2、剑指offerII：

力扣总记录数：

加油加油！

剑指offer

剑指 Offer 31. 栈的压入、弹出序列【中等】

题目链接：剑指 Offer 31. 栈的压入、弹出序列

题目内容：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

思路：利用栈

1、借用栈，先入栈，接着来进行尝试出栈操作，若是最终栈中没有元素了，说明true。

复杂度分析：时间复杂度O(n)、空间复杂度O(n)

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for (int num: pushed) {
            stack.push(num);//先进行入栈
            while (!stack.isEmpty() && stack.peek() == popped[i]) {
                stack.pop();
                i++;
            }
        }
        return stack.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

牛客网

包含min函数的栈【简单】

题目链接： 包含min函数的栈

题目内容：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

思路：采用两个栈来进行处理操作。

复杂度分析：

• 时间复杂度：O(1)
• 空间复杂度：O(n)

import java.util.*;
import java.util.Stack;

public class Solution {
    
    //栈1存储元素；栈2存储最小元素
    private Stack<Integer> stack1 = new Stack<Integer>();
    private Stack<Integer> stack2 = new Stack<Integer>();
    
    public void push(int node) {
        stack1.push(node);
        //若是当前栈2为空且当前元素<栈顶元素
        if (stack2.isEmpty() || node < stack2.peek()) {
            stack2.push(node);
        }else{
            stack2.push(stack2.peek());
        }
    }
    
    public void pop() {
        stack1.pop();
        stack2.pop();
    }
    
    public int top() {
        return stack1.peek();
    }
    
    public int min() {
        return stack2.peek();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

有效括号序列【简单】

学习：leetcode题解、 代码随想录—有效的括号

题目链接：有效括号序列

题目内容：给出一个仅包含字符’(‘,’)‘,’{‘,’}‘,’[‘和’]',的字符串，判断给出的字符串是否是合法的括号序列括号必须以正确的顺序关闭，"()“和”()[]{}“都是合法的括号序列，但”(]“和”([)]"不合法。

思路：借助栈数据结构，总共有三个类型[]{}()，若是碰到前半个，那么就入栈后半缀，若是非后半缀进行出栈并且进行比较即可！

• 若是左闭合符号就压入配对的右闭合符号，方便之后进行匹配。

示例："()[{}]"   stack=[]
① 字符'('，压入')'  stack=['(']
② 字符')'，与当前栈顶存放匹配，出栈  stack=[]
③ 字符'['，压入']'  stack=[']']
④ 字符'{'，压入'}'  stack=[']','}']
⑤ 字符'}'，与当前栈顶存放匹配，出栈 stack=[']']
⑥ 字符']'，与当前栈顶存放匹配，出栈 stack=[]
所有字符都遍历一遍之后，判断栈中是否存在元素，为空表示有效括号；不为空表示无效括号。
1
2
3
4
5
6
7
8

复杂度分析：

• 时间复杂度：O(n)，其中n为字符串长度，遍历整个字符串。
• 空间复杂度：O(n)，最坏情况下记录整个字符串的右括号。

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return bool布尔型
     */
    public boolean isValid (String s) {
        //定义一个栈
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0;i < s.length();i++) {
            Character ch = s.charAt(i);
            //三种情况：{}()[]
            if (ch == '{'){
                stack.push('}');
            }else if (ch == '(') {
                stack.push(')');
            }else if (ch == '['){
                stack.push(']');
            }else if (stack.isEmpty() || stack.pop() != ch) {
                return false;
            }
        }
        return stack.isEmpty();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

表达式求值【中等】

题目链接：表达式求值

题目内容：请写一个整数计算器，支持加减乘三种运算和括号。

思路：双栈操作。一个栈存储运算符，另一个栈存储数字（及运算结果）

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(n)

import java.util.*;


public class Solution {
    
    private Map<Character, Integer> map = new HashMap<Character, Integer>(){
        {
            put('-', 1);
            put('+', 1);
            put('*', 2);
        }
    };
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    //触发计算的几种情况：①碰到)。②新运算符即将入栈【判断前栈中的一个运算符是否等级高于当前要插入的，若是>=那么先进行计算】。③整个字符串遍历结束后将栈中的进行处理。
    public int solve (String s) {
        //使用两个栈
        Stack<Character> ops = new Stack<>();
        Stack<Integer> nums = new Stack<>();
        //将所有的空格去除掉
        s = s.replaceAll(" ", "");
        int length = s.length();
        //开始进行遍历
        for (int i = 0;i < length;i++) {
            char ch = s.charAt(i);
            if (ch == '(') {
                ops.push(ch);
            }else if (ch == ')') {
                //开始进行计算()中的表达式
                while (!ops.isEmpty() && ops.peek() != '(') {
                    calc(nums, ops);
                }
                //将ops中最后一个(移除
                ops.pop();
            }else if (isNumber(ch)) {
                //可能是十位数、百位数...
                int num = 0;
                int j = i;
                while (j < length && isNumber(s.charAt(j))) {
                    //注意：这里需要j++
                    num = num * 10 + s.charAt(j++) - '0';
                }
                //添加到栈中
                nums.push(num);
                i = j - 1;//因为for循环之后会i++，j此时肯定在非数字上目前
            }else {
                //非(、)、数字情况
                //1、+*-，待插入的是-，此时栈中有运算符优先级更高的
                while (!ops.isEmpty() && ops.peek() != '(') {
                    Character peekCh = ops.peek();
                    //若是当前在栈中权重更高，那么优先进行计算栈中的元素
                    if (map.get(peekCh) >= map.get(ch)) {
                        calc(nums, ops);
                    }else {
                        break;
                    }
                }
                //将新的运算符入栈
                ops.push(ch);
            }
        }
        //遍历完成之后，还要进行剩余内容的计算
        while (!ops.isEmpty()) {
            calc(nums, ops);
        }
        return nums.pop();
    }
    
    //计算运算符
    public void calc(Stack<Integer> nums, Stack<Character> ops) {
        if (nums.size() < 2 && ops.size() < 1) {
            return;
        }
        //取出一个符号
        char ch = ops.pop();
        Integer num2 = nums.pop();
        Integer num1 = nums.pop();
        int res = 0;
        if (ch == '+') {
            res = num1 + num2;
        }else if (ch == '-') {
            res = num1 - num2;
        }else if (ch == '*') {
            res = num1 * num2;
        }
        nums.push(res);
    }
    
    public boolean isNumber(Character ch) {
        return Character.isDigit(ch);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

leetcode

232. 用栈实现队列【简单】

学习：leetcode题解、 代码随想录—232.用栈实现队列

题目链接：232. 用栈实现队列

题目内容：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

思路：

1、双栈实现队列

思路： 一个栈用来进行进栈(栈1)，另一个栈用来出栈(栈2)。出栈的时候，先判断栈2是否为空，为空了统一将栈1中的元素依次出栈进栈2，不为空不进行该操作，避免有些后进的之后被pop出去。

class MyQueue {

    private Stack<Integer> stack1;//负责进栈
    private Stack<Integer> stack2;//负责出栈

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        dumpStack1();
        return stack2.pop();
    }

    public int peek() {
        dumpStack1();
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }

    public void dumpStack1(){
        //判断栈2是否为空，空了才会将stack1的元素压入(避免后进的元素入了栈2)
        if(stack2.isEmpty()){
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

---

1047. 删除字符串中的所有相邻重复项【中等】

学习：leetcode题解、 代码随想录—删除字符串中的所有相邻重复项

题目链接：1047. 删除字符串中的所有相邻重复项

题目内容：

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：
1 <= S.length <= 20000
S 仅由小写英文字母组成。
1
2
3
4
5
6
7
8
9
10
11
12
13

思路：

1、栈解决

思路：遍历字符时，每次先判断当前栈顶元素是否与要入栈的元素相同，如果相同出栈，不相同入栈。最后将栈中的字符进行一一拼接返回。

示例："abbaca" stack=[]
① 字符'a'，当前栈为空直接入栈  stack=['a']
② 字符'b'，栈不为空，与栈顶元素a比较，不相同入栈  stack=['a','b']
③ 字符'b'，栈不为空，与栈顶元素b比较，相同出栈  stack=['a']
④ 字符'a'，栈不为空，与栈顶元素b比较，相同出栈  stack=[]
⑤ 字符'c'，当前栈为空直接入栈  stack=['c']
⑥ 字符'a'，栈不为空，与栈顶元素c比较，不相同入栈  stack=['a','c']
最终从前往往后将元素移出进行拼接，返回"ac"
1
2
3
4
5
6
7
8

代码：

class Solution {
    public String removeDuplicates(String s) {
        Deque<Character> stack = new LinkedList<>();
        for (char c : s.toCharArray()) {
            //当前栈不为空，且栈顶与当前字符相同出栈
            if(!stack.isEmpty() && stack.peek() == c){
                stack.pop();
            }else{//否则直接入栈
                stack.push(c);
            }
        }
        StringBuilder str = new StringBuilder();
        while(!stack.isEmpty()){
            str = str.append(stack.pollLast());
        }
        return str.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2、字符串作栈

思路：使用字符串作栈的好处就是可以省去上面提交中拼接的操作，最终留在字符串里的就是要返回出去的。

示例："abbaca"  str="" top=-1
① 字符'a' 字符串(栈)为空，直接拼接 str="a"  top=0
② 字符'b' 字符串(栈)不为空，与栈顶不相同，直接拼接 str="ab" top=1
③ 字符'b' 字符串(栈)不为空，与栈顶相同，删除指定元素 str="a" top=0
④ 字符'a' 字符串(栈)不为空，与栈顶相同，删除指定元素 str="" top=-1
⑤ 字符'c' 字符串(栈)为空，直接拼接 str="c"  top=0
⑥ 字符'b' 字符串(栈)不为空，与栈顶不相同，直接拼接 str="ca" top=1
最终直接返回str="ca"   
1
2
3
4
5
6
7
8

代码：

class Solution {
    //目的是拿到不重复的字符拼接内容
    public String removeDuplicates(String s) {
        //直接来拿字符串来作为栈进行操作，最终剩下来的就是不重复的
        StringBuilder str = new StringBuilder();
        int top = -1;
        for (char c : s.toCharArray()) {
            if(top >= 0 && c == str.charAt(top)){
                str.deleteCharAt(top--);
            }else{
                str.append(c);
                top++;
            }
        }
        return str.toString();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3、双指针（原数组上操作）

思路：直接对原数组进行操作，不相邻的重复元素直接覆盖旧元素，最终直接截取原数组指定长度内容返回。

fast指针用来进行遍历一遍字符串的，[0,slow)永远表示的是非相邻重复项
示例：s="abbaca"  slow=0,fast=0
① 字符'a' s[0]=s[0] (s="abbaca") slow=1,fast=1  | [0,slow)=> "a"
② 字符'b' s[1]=s[1] (s="abbaca") slow=2,fast=2  | [0,slow)=> "ab"
③ 字符'b' s[2]=s[2] (s="abbaca")(s[2]==s[1] => b=b重复，slow-1) slow=1,fast=3    | [0,slow)=> "a"
④ 字符'a' s[1]=s[3] (s="aabaca")(s[1]==s[0] => a=a重复，slow-1) slow=0,fast=4    | [0,slow)=> ""
⑤ 字符'c' s[0]=s[4] (s="cabaca")(slow=0，slow+1) slow=1,fast=5     | [0,slow)=> "c"
⑥ 字符'a' s[1]=s[5] (s="cabaca")(s[1]!=s[0]，slow++) slow=1,fast=4    | [0,slow)=> "ca"
最终直接返回"ca"即可
1
2
3
4
5
6
7
8
9

代码：

//快慢指针，时间复杂度O(n)，空间复杂度O(1)
public String removeDuplicates(String s) {
    //定义双指针
    int slow = 0;//左指针的目的是①检测是否有相等，有后退，无前进。②实时更新当前最新位置值(方便下次进行对比以及旧值的覆盖，旧的值已无用)
    int fast = 0;//右指针负责的工作是进行遍历作用
    char[] chars = s.toCharArray();
    while(fast < s.length()){
        chars[slow] = chars[fast];
        if(slow > 0 && chars[slow]==chars[slow-1]){
            slow--;
        }else{
            slow++;
        }
        fast++;
    }
    //[0,slow)区间值
    return new String(chars,0,slow);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

150. 逆波兰表达式求值【中等】

学习：leetcode题解、 代码随想录—150. 逆波兰表达式求值

题目链接：150. 逆波兰表达式求值

题目内容：

根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
1
2
3
4

思路：

1、栈解决（后缀表达式）

题目给的就是后缀表达式

思路：若是数字直接入栈，碰到运算符出栈两次进行相应运算后，将运算结果入栈，之后重复即可。其中需要注意的是给的是字符串数组，需要进行转换以及要注意/、-时，要拿后出栈的运算前出栈的。

示例：["2", "1", "+", "3", "*","3", "/" , "5" , "-"]  stack=[]
① "2" 是数字直接转换入栈  stack=[2]
② "1" 是数字直接转换入栈  stack=[2,1]
③ "+" 是运算符，出栈两次 第一次出1，第二次2 1+2=3入栈 stack=[3]
④ "3" 是数字直接转换入栈  stack=[3,3]
⑤ "*" 是运算符，出栈两次 第一次出3，第二次3 3*3=9入栈 stack=[9]
⑥ "3" 是数字直接转换入栈  stack=[9,3]
⑦ "/" 是运算符，出栈两次 第一次出3，第二次9 注意这里要拿后一个除前一个9/3=3入栈 stack=[3]
⑧ "5" 是数字直接转换入栈  stack=[3,5]
⑨ "-" 是运算符，出栈两次 第一次出5，第二次3 注意这里要拿后一个减前一个3-5=-2入栈 stack=[-2]
最后出栈即为结果-2
1
2
3
4
5
6
7
8
9
10
11

代码：

public int evalRPN(String[] tokens) {
    Deque<Integer> stack = new LinkedList<>();
    for (String token : tokens) {
        //若是数字
        if (!isOper(token)) {
            stack.push(Integer.valueOf(token));
        } else if (Objects.equals("+", token)) {
            stack.push(stack.pop() + stack.pop());
        } else if (Objects.equals("-", token)) {
            stack.push(-stack.pop() + stack.pop());//－的话，要注意出栈元素熟悉，后出的-先出的
        } else if (Objects.equals("*", token)) {
            stack.push(stack.pop() * stack.pop());
        } else {
            //除法操作与上面的同理，后出的/先出的
            int num2 = stack.pop();
            int num1 = stack.pop();
            stack.push(num1 / num2);
        }
    }
    return stack.pop();
}

//判断是否为运算符
public boolean isOper(String str) {
    if (str.length() == 1 && (str.charAt(0) < '0' || str.charAt(0) > '9')) {
        return true;
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29