辅助栈
# 155. 最小栈 - 力扣（LeetCode） (opens new window)
class MinStack {
Deque<Integer> stack;
Deque<Integer> minStack;
public MinStack() {
stack=new LinkedList<Integer>();
minStack=new LinkedList<Integer>();
minStack.push(Integer.MAX_VALUE);
}
public void push(int val) {
stack.push(val);
minStack.push(Math.min(minStack.peek(),val));
}
public void pop() {
stack.pop();
minStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.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
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
# 20. 有效的括号 - 力扣（LeetCode） (opens new window)
class Solution {
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();
}
}
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
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
# 224. 基本计算器 - 力扣（LeetCode） (opens new window)
class Solution {
public int calculate(String s) {
int res = 0;
int num = 0;
int sign = 1;
Stack<Integer> stack = new Stack();
char[] chars = s.toCharArray();
int len = chars.length;
for(int i = 0; i < len; i++){
char c = chars[i];
if (c == ' ') continue;
// 如果当前字符是一个数字，则用num进行记录
if (c >= '0' && c <= '9'){
num = num * 10 + c - '0';
// 判断当前数字是否已经取完
if(i < len - 1 && '0' <= chars[i+1] && chars[i+1] <= '9'){
continue;
}
} else if (c == '+' || c == '-'){
// 将num置为0，用来存放当前符号(+/-)之后的数字
num = 0;
sign = c=='+' ? 1:-1;
} else if (c == '('){
stack.push(res);
stack.push(sign);
res = 0;
sign = 1;
} else if (c == ')'){
// '('前边的符号出栈
sign = stack.pop();
// 将num替换为括号中的计算结果
num = res;
// 将res替换为括号前边的计算结果
res = stack.pop();
}
res += sign * num;
}
return res;
}
}
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
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
# 946. 验证栈序列 - 力扣（LeetCode） (opens new window)
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
2
3
4
5
6
7
8
9
10
11
12
13
14
# 232. 用栈实现队列 - 力扣（LeetCode） (opens new window)
class MyQueue {
Deque<Integer> inStack;
Deque<Integer> outStack;
public MyQueue() {
inStack = new LinkedList<Integer>();
outStack = new LinkedList<Integer>();
}
public void push(int x) {
inStack.push(x);
}
public int pop() {
if(outStack.isEmpty()){
while(!inStack.isEmpty()){
outStack.push(inStack.pop());
}
}
return outStack.pop();
}
public int peek() {
if(outStack.isEmpty()){
while(!inStack.isEmpty()){
outStack.push(inStack.pop());
}
}
return outStack.peek();
}
public boolean empty() {
return inStack.isEmpty() && outStack.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
29
30
31
32
33
34
35
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
# 单调栈
# 739. 每日温度 - 力扣（LeetCode） (opens new window)
示例
输入: T= [73,74,75,71,69,72,76,73]
我们从后往前遍历：
stack=[]
7（73）. 栈没有元素，返回0，加入自己的下标
stack=[7] 堆栈=[7]
6（76）. 弹出所有比自己小的元素，T[7]
stack=[6] 堆栈=[6]
5（72）. 没有比自己小的元素，返回 栈顶（6）-当前下标=1 ，加入自己的下标
stack=[6,5] 堆栈=[6,5]
4（69）. 没有比自己小的元素，返回 栈顶（5）-当前下标=1 ，加入自己的下标
stack=[6,5,4] 堆栈=[6,5,4]
3（71）. 栈顶4对应的69比我小，弹出！返回 栈顶（5）-当前下标=2 ，加入自己的下标
stack=[6,5,3] 堆栈=[6,5,3]
2（75）. 栈3和5对应的71和72比我小，弹出！返回 栈顶（6）-当前下标=4 ，加入自己的下标
stack=[6,2] 堆栈=[6,2]
1（74）. 没有比自己小的元素，返回 栈顶（2）-当前下标=1 ，加入自己的下标
stack=[6,2,1] 堆栈=[6,2,1]
0（73）. 没有比自己小的元素，返回 栈顶（1）-当前下标=1 ，加入自己的下标
stack=[6,2,1,0] 堆栈=[6,2,1,0]
所以我们就得到输出 answer = [1,1,4,2,1,1,0,0]
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int[] ans=new int[temperatures.length];
//存储下标
Stack<Integer> st = new Stack<>();
//从后往前遍历
for(int i = temperatures.length - 1;i >= 0; i--){
//自顶向下弹出所有比当前温度小的
while(!st.isEmpty() && temperatures[i] >= temperatures[st.peek()]){
st.pop();
}
//如果栈空了说明后面没有比自己大的，答案是0;否则是栈顶下标和自己下标的差
ans[i] = st.isEmpty() ? 0 : st.peek() - i;
//加入当前温度下标
st.push(i);
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# 402. 移掉 K 位数字 - 力扣（LeetCode） (opens new window)
可能你会问：什么时候用单调栈？
需要给当前的元素，找右边/左边第一个比它大/小的位置。
记住这两句话：
单调递增栈，利用波谷剔除栈中的波峰，留下波谷；
单调递减栈，利用波峰剔除栈中的波谷，留下波峰。
本题想维护高位递增，即，元素想找右边第一个比它小的数，即右侧第一个波谷。
单调递增栈遇到波谷，用它来剔除栈中的波峰，维持单增。
留下波谷保持了单增，而剔除掉的栈中字符，就是删掉的字符。
class Solution {
public String removeKdigits(String num, int k) {
Deque<Character> stack = new ArrayDeque<>(num.length());
for (char c: num.toCharArray()) {
// 只要k>0且当前的c比栈顶的小，则栈顶出栈，k--
while (k > 0 && !stack.isEmpty() && c < stack.peek()) {
stack.pop();
k--;
}
// 当前的字符不是"0"，或栈非空（避免0入空栈），入栈
if (c!='0' || !stack.isEmpty()) {
stack.push(c);
}
}
//// 如果还没删够，要从stack继续删，直到k=0
while (k > 0 && !stack.isEmpty()) {
stack.pop();
k--;
}
StringBuffer buffer = new StringBuffer();
while (!stack.isEmpty()) {
buffer.append(stack.pollLast());
}
return buffer.length() == 0 ? "0" : buffer.toString();
}
}
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
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
编辑 (opens new window)
上次更新: 2025/06/13, 00:51:28