力扣热题100---栈

1.有效的括号
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

解题思路：
手动用StringBuffer模拟一个栈，遍历字符串：
（1）当遍历到’(’、’{’、’[‘时把他们放入StringBuffer中
（2）当遍历到’)’、’}’、’]'时判断StringBuffer中最后一个符号是否与之对应:

①对应就删除最后的符号，继续遍历;
②不对应直接返回false。

charAt(i):将字符串下标为i的字符转化为char类型
deleteCharAt(i):删除索引为a的字符
delete(i,j):有两个参数，使用时删除索引从a开始（包含a）到b（不包含b）的所有字符

StringBuffer ant = new StringBuffer();
        int n = s.length();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                ant.append(c);
            }else{
                if(ant.length()==0){
                    return false;
                }
                char cc = ant.charAt(ant.length() - 1);
                if ((cc == '(' && c == ')') || (cc == '[' && c == ']') || (cc == '{' && c == '}')) {
                    ant.deleteCharAt(ant.length()- 1);
                    continue;
                }else {
                    return false;
                }
            }
        }
        return (ant.length()==0);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素
1
2
3
4

方法：辅助栈
思路：
进栈（push）：当目标栈有元素要进栈时，与辅助栈的元素进行比较，将比较得到的最小元素进栈辅助栈，
peek():读取一个字符，将其返回值是一个char型的字符
Math.min(x,y)

class MinStack {

    Deque<Integer> xStack;
    Deque<Integer> minStack;
    /** initialize your data structure here. */
    public MinStack() {
        xStack =new LinkedList<Integer>();
        minStack=new LinkedList<Integer>();
        minStack.push(Integer.MAX_VALUE);
    }
    
    public void push(int val) {
        xStack.push(val);
        minStack.push(Math.min(minStack.peek(),val));
    }
    
    public void pop() {
        xStack.pop();
        minStack.pop();
    }
    
    public int top() {
        return xStack.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
28
29