算法
算法

经典算法-栈

用栈来实现队列

可以通过两个栈实现队列，输入数据都压入输入栈，获取数据时若输出栈为空则将输入栈中的数据压入输出栈再出栈

字符串解码

通过栈的方式来实现，一开始一直入栈，当出现右中括号时出栈，出栈结束位置为数字出完

1
// 394. 字符串解码

单调栈

每日温度

给定整数数组temperatures表示每天温度，返回一个数组answer，answer[i]是指在第i天之后，才会有更高的温度。若气温在这之后都不会升高，则在该位置用0来代替。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int[] dailyTemperatures(int[] temperatures) {
    int len = temperatures.length;
    int[] res = new int[len];
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < res.length; i++) {
        int temperature = temperatures[i];
        while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
            int prevIndex = stack.pop();
            res[prevIndex] = i - prevIndex;
        }
        stack.push(i);
    }
    return res;
}

最长有效括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int longestValidParentheses(String s) {
    int max = 0;
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    int len = s.length();
    for (int i = 0; i < len; i++) {
        if (s.charAt(i) == '(') {
            stack.push(i);
        } else {
            stack.pop();
            if (stack.isEmpty()) {
                stack.push(i);
            } else {
                max = Math.max(max, i - stack.peek());
            }
        }
    }
    return max;
}