hot100之栈

有效的括号(020)

跳过
最小栈(155)

1. class MinStack {
2.     private final Deque<int[]> stack = new ArrayDeque<>();
4.     public MinStack() {
5.         stack.addLast(new int[]{0, Integer.MAX_VALUE});
6.     }
7.     public void push(int val) {
8.         stack.addLast(new int[]{val, Math.min(stack.peekLast()[1], val)});
9.     }
10.     public void pop() {
11.         stack.removeLast();
12.     }
13.     public int top() {
14.         return stack.peekLast()[0];
15.     }
16.     public int getMin() {
17.         return stack.peekLast()[1];
18.     }
19. }

复制代码

• 分析
  

使用双端队列作栈
利用动态规划, 每个栈元素维护自身val和min_val
字符串解码(394)

1. class Solution {
2.     public String decodeString(String s) {
3.         int idx = 0;
4.         StringBuilder builder = new StringBuilder();
5.         while (idx < s.length()){
6.             // 是字母
7.             if (s.charAt(idx) >= 'a'){
8.                 builder.append(s.charAt(idx));
9.                 idx++;
10.                 continue;
11.             }
12.             idx = appendDupString(idx, s, builder);
13.             //是数字
14.         }
15.         return builder.toString();
16.     }
18.     private int appendDupString(int idx, String s , StringBuilder builder){
19.         int prefix_count = 0;
21.         while(s.charAt(idx) != '['){
22.             prefix_count = prefix_count * 10 + s.charAt(idx) - '0';
23.             idx++;
24.         }
26.         int rig_idx = idx+1;
27.         int nest = 1;
28.         while (nest != 0){
29.             if (s.charAt(rig_idx) == '[') nest++;
30.             else if (s.charAt(rig_idx) == ']') nest--;
31.             rig_idx++;
32.         }
34.         String subString = decodeString(s.substring(idx+1, rig_idx-1));
35.         for (int i = 0; i < prefix_count; i++){
36.             builder.append(subString);
37.         }
38.         return rig_idx;
39.     }
40. }

复制代码

• 分析
  

递归调用
每日温度(739)

栈解法

1. class Solution {
2.     public int[] dailyTemperatures(int[] temperatures) {
3.         int n = temperatures.length;
4.         int[] res = new int[n];
6.         Deque<Integer> stack = new ArrayDeque<>();
7.         for (int i = n-1; i >= 0; i--){
8.             int t = temperatures[i];
9.             while(!stack.isEmpty() && t >=temperatures[stack.peek()]){
10.                 stack.pop();
11.             }
12.             if (!stack.isEmpty()){
13.                 res[i] = stack.peek() - i;
14.             }
15.             stack.push(i);
16.         }
18.         return res;
19.     }
20. }

复制代码

跳表解法

1. class Solution {
2.     public int[] dailyTemperatures(int[] temperatures) {
3.         int n = temperatures.length;
4.         int[] res = new int[n];
6.         for (int i = n-2; i >= 0; i--){
7.             for (int j = i+1; j < n; j += res[j]){
8.                 if (temperatures[j] > temperatures[i]){
9.                     res[i] = j - i;
10.                     break;
11.                 }
12.                 else if (res[j] == 0){
13.                     res[i] = 0;
14.                     break;
15.                 }
16.             }
17.         }
18.         return res;
19.     }
20. }

复制代码

• 分析
  

栈解法
栈用于维护数据
维护栈的单调性就是在维护栈组中的数据的性, 栈自身的性质可以用于保持特性
跳表解法
可能也许这是贪心
柱状图中最大矩形(084)

[code]class Solution {    public int largestRectangleArea(int[] heights) {        int n = heights.length;        Deque stack = new ArrayDeque();        stack.push(-1);        int res = 0;        for (int rig = 0; rig  1 && h