青铜挑战—手撕栈
内容大纲
- 数组栈
- 链表栈
数组栈
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
| public class AStack<T> {
private T[] stack;
private int top;
public AStack() {
this.stack = (T[]) new Object[10];
}
public boolean isEmpty() {
return top == 0;
}
public T peek() {
T t = null;
if (top > 0) {
t = stack[top - 1];
}
return t;
}
public T pop() {
T t = peek();
if (top > 0) {
stack[top - 1] = null;
top--;
}
return t;
}
public void push(T t) {
expandCapacity(top + 1);
stack[top++] = t;
}
public void expandCapacity(int size) {
int length = stack.length;
if (size > length) {
size = size * 3 / 2 + 1;
stack = Arrays.copyOf(stack, size);
}
}
}
|
链表栈
链表实现栈：在头节点进行插入和删除节点
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
| public class LStack<T> {
class Node<T> {
public T data;
public Node next;
}
public Node<T> head;
public LStack() {
this.head = null;
}
public void push(T t) {
if (t == null) {
throw new NullPointerException("参数不能为空");
}
if (head == null) {
head = new Node<>();
head.data = t;
head.next = null;
} else {
Node<T> temp = head;
head = new Node<>();
head.data = t;
head.next = temp;
}
}
public T pop() {
if (head == null) {
return null;
}
T t = head.data;
head = head.next;
return t;
}
public T peek() {
if (head == null) {
return null;
}
return head.data;
}
public boolean isEmpty() {
return head == null;
}
}
|
白银挑战—栈经典算法
内容大纲
- 括号匹配问题
- 最小栈
- 最大栈
括号匹配问题
问题
【LettCode 20】：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
算法思路
- 当遇到一个左括号时，会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此可以将这个左括号放入栈顶。
- 当遇到一个右括号时，需要将一个相同类型的左括号闭合。此时，可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号，那么字符串 s 无效，返回 False。
为快速判断括号的类型，可以使用哈希表存储每一种括号。哈希表的键为右括号，值为相同类型的左括号。
在遍历结束后，如果栈中没有左括号，说明将字符串 s 中的所有左括号闭合，返回 True，否则返回 False。
注意到有效字符串的长度一定为偶数，因此如果字符串的长度为奇数，我们可以直接返回 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
| public boolean isValid(String s) {
if (s.length() % 2 == 1) {
return false;
}
Map<Character, Character> pairs = new HashMap<>();
pairs.put(')', '(');
pairs.put('}', '{');
pairs.put(']', '[');
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); 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();
}
|
扩展
LeetCode 22.括号生成
LeetCode 32.最长有效括号
LeetCode 301.删除无效的括号
LeetCode 856.括号的分数
最小栈
问题
【LeetCode 155】：设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 输入：
["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.
|
注意
题目要求在常数时间内获得栈最小值，因此不能在 getMin() 时再计算最小值
栈的性质
对于栈来说，如果一个元素 a 在入栈时，栈里有其它的元素 b, c, d，那么无论这个栈在之后经历了什么操作，只要 a 在栈中，b, c, d 就一定在栈中，因为在 a 被弹出之前，b, c, d 不会被弹出。
因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么我们就可以确定栈里面现在的元素一定是 a, b, c, d。
那么，我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m。
只需要设计一个数据结构，使得每个元素 a 与其相应的最小值 m 时刻保持一一对应，可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。
当一个元素要入栈时，取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；
当一个元素要出栈时，把辅助栈的栈顶元素也一并弹出；
在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。
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
| public class MinStack {
private Deque<Integer> stack;
private Deque<Integer> minStack;
public MinStack() {
stack = new LinkedList<>();
minStack = new LinkedList<>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int x) {
stack.push(x);
minStack.push(Math.min(x, minStack.peek()));
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
|
最大栈
问题
【LeetCode 716】：设计一个支持 push，pop，top 操作，并能在常数时间内检索到最大元素的栈。
实现 MaxStack 类：
MaxStack() 初始化栈对象push(x) 将元素 x 压入栈中pop() 移除栈顶元素并返回这个值top() 返回栈顶元素peekMax() 返回栈中最大元素popMax() 返回栈中最大的元素，并将其删除 如果有多个最大元素，只要删除最靠近栈顶的那个。
1
2
3
4
5
6
7
8
9
10
| MaxStack stack = new MaxStack();
stack.push(5);
stack.push(1);
stack.push(5);
stack.top(); -> 5
stack.popMax(); -> 5
stack.top(); -> 1
stack.peekMax(); -> 5
stack.pop(); -> 1
stack.top(); -> 5
|
peekMax
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
| public class MaxStack {
private Deque<Integer> stack;
private Deque<Integer> maxStack;
public MaxStack() {
this.stack = new LinkedList<>();
this.maxStack = new LinkedList<>();
}
public void push(int x) {
int max = maxStack.isEmpty() ? x : maxStack.peek();
maxStack.push(max > x ? max : x);
stack.push(x);
}
public int pop() {
maxStack.pop();
return stack.pop();
}
public int top() {
return stack.peek();
}
public int peekMax() {
return maxStack.peek();
}
public int popMax() {
int max = peekMax();
Deque<Integer> temp = new LinkedList<>();
while (top() != max) {
temp.push(pop());
}
pop();
while (!temp.isEmpty()) {
push(temp.pop());
}
return max;
}
}
|
黄金挑战—表达式问题
计算器问题
逆波兰表达式
