(伪)栈
| 最近提交时间 | 题目 | 题目难度 | 提交次数 |
|---|---|---|---|
| 7 分钟前 | #84 柱状图中最大的矩形 | 困难 | 4 次 |
| 20 分钟前 | #739 每日温度 | 中等 | 4 次 |
| 30 分钟前 | #394 字符串解码 | 中等 | 1 次 |
| 2 小时前 | #155 最小栈 | 中等 | 1 次 |
| 2 小时前 | #20 有效的括号 | 简单 | 11 次 |
为什么叫（伪）栈？
是因为有些题目，直接蛮力法做，或者利用奇淫巧技更为简单。
面试在栈不熟的情况下（尤其是单调栈这种<温度，雨水等>），直接两层for搞定 ，虽然超时，但面试不扣分
备注：
1、有效括号 包含时放入栈中的是value if条件下直接返回false 包含value时 的判断 !stack.pop().equals(c)
2、最小栈 除去pop外 都是 peek操作
3、字符串解码 （过）
4、每日温度 ，倒着循环，内部 对 j while循环 记录值 每一步完成都要break；
5、柱状图 最大矩形 就按照这个做
int res = 0;
for(int i = 0; i< heights.length; i++){
int l = Integer.MAX_VALUE;
for(int j = i; j< heights.length; j++){
l = Math.min(l, heights[j]);
res = Math.max(res, l*(j-i+1));
}
}
return res;
# 有效括号
class Solution {
public boolean isValid(String s) {
Map<Character, Character> map = new HashMap<>();
map.put('(', ')');
map.put('[', ']');
map.put('{', '}');
Stack<Character> stack = new Stack();
for(int i = 0; i< s.length(); i++){
char c = s.charAt(i);
if(map.containsKey(c)){
stack.push(map.get(c));
}
if(map.containsValue(c)){
if(stack.isEmpty()){
return false;
}
if(!stack.pop().equals(c)){
return false;
}
}
}
return stack.isEmpty();
}
}
思路：
1、利用了栈 + 奇淫巧技
2、先定义一个限定的map
3、然后循环字符串，如果map的key包含 char 就放入 栈
4、否则 判断是否包含value ，之后 如果栈是空的直接返回false（这就是 括号不对称的场景
5、然后将栈pop 判断是否与当前char 相等，不相等就是false
6、最后如果栈是空的 那就是完美 括弧， 只要栈里面有没弹出来的 就是不完美的
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
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
# 最小栈
class MinStack {
Stack<Integer> stack;
Stack<Integer> help;
public MinStack() {
stack =new Stack<>();
help = new Stack<>();
}
public void push(int val) {
stack.push(val);
if(help.isEmpty() || help.peek() >= val){
help.push(val);
} else{
help.push(help.peek());
}
}
public void pop() {
if(!stack.isEmpty()){
stack.pop();
help.pop();
}
}
public int top() {
if(!stack.isEmpty()){
return stack.peek();
}
throw new RuntimeException("栈中元素为空，此操作非法");
}
public int getMin() {
if(!help.isEmpty()){
return help.peek();
}
throw new RuntimeException("栈中元素为空，此操作非法");
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(val);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
思路：
1、定义一个辅助栈
2、getmin 就是 help 出栈
3、top 就是 stack 出栈
4、pop 只要 stack不是空的 就一起pop
5、push stack直接 push 然后help 首先是空的 并且help 当前val 比 peek后的元素 小 才会放入help 否则 help元素就自己放入自己。
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
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
# 字符串解码
class Solution {
public String decodeString(String s) {
while (s.contains("[")) {
Pattern pattern = Pattern.compile("(\\d+)\\[([a-z]+)\\]");
Matcher matcher = pattern.matcher(s);
if (matcher.find()) {
int n = Integer.parseInt(matcher.group(1));
String str = matcher.group(2);
// 用字符串补齐方法将 n 个 s 拼接 替换掉编码
String replacement = new String(new char[n]).replace("\0", str);
s = s.replaceFirst("(\\d+)\\[([a-z]+)\\]", replacement);
} else {
break;
}
}
return s;
}
}
思路：
1、奇淫巧技了 ，正则不好搞 ，但写出来很装杯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 每日温度
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
// int[] answer = new int[temperatures.length];
// for(int i = 0; i< temperatures.length; i++){
// int now = temperatures[i];
// for(int j = i+1; j< temperatures.length; j++){
// int next = temperatures[j];
// if(next > now){
// answer[i] = j-i;
// break;
// }
// }
// }
// return answer;
int[] res = new int[temperatures.length];
//从后面开始查找
for (int i = res.length - 1; i >= 0; i--) {
int j = i + 1;
while (j < res.length) {
if (temperatures[j] > temperatures[i]) {
//如果找到就停止while循环
res[i] = j - i;
break;
} else if (res[j] == 0) {
//如果没找到，并且res[j]==0。说明第j个元素后面没有
//比第j个元素大的值，因为这一步是第i个元素大于第j个元素的值，
//那么很明显这后面就更没有大于第i个元素的值。直接终止while循环。
break;
} else {
//如果没找到，并且res[j]！=0说明第j个元素后面有比第j个元素大的值，
//然后我们让j往后挪res[j]个单位，找到那个值，再和第i个元素比较
j += res[j];
}
}
}
return res;
}
}
思路：
1、第一种方法 暴力破解，简单 但是时间复杂度不符合
2、第二种 在暴力破解的基础上 优化 利用找不到就停止循环和跳跃多个元素的方式 进行判断比较 致使时间复杂度来到 n*log（n）
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
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
# 柱状图中最大的矩形
class Solution {
// public int largestRectangleArea(int[] heights) {
// // int ans = 0;
// // for(int left =0; left< heights.length; left++){
// // int height = Integer.MAX_VALUE;
// // for(int right = left; right < heights.length; right++){
// // height = Math.min(height , heights[right]);
// // ans = Math.max(ans, (right-left+1) * height);
// // }
// // }
// // return ans;
// }
public int largestRectangleArea(int[] heights) {
// 这里为了代码简便，在柱体数组的头和尾加了两个高度为 0 的柱体。
int[] tmp = new int[heights.length + 2];
System.arraycopy(heights, 0, tmp, 1, heights.length);
Deque<Integer> stack = new ArrayDeque<>();
int area = 0;
for (int i = 0; i < tmp.length; i++) {
// 对栈中柱体来说，栈中的下一个柱体就是其「左边第一个小于自身的柱体」；
// 若当前柱体 i 的高度小于栈顶柱体的高度，说明 i 是栈顶柱体的「右边第一个小于栈顶柱体的柱体」。
// 因此以栈顶柱体为高的矩形的左右宽度边界就确定了，可以计算面积🌶️ ～
while (!stack.isEmpty() && tmp[i] < tmp[stack.peek()]) {
int h = tmp[stack.pop()];
area = Math.max(area, (i - stack.peek() - 1) * h);
}
stack.push(i);
}
return area;
}
}
思路：
1、暴力破解，但要注意height的判断，其余就是双循环赋值面积而已， 但是缺点就是时间超时
2、第二个单调栈 理解起来还是要麻烦一点的。
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
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
上次更新: 2024/03/26, 9:03:00