【LeetCode】四、栈相关：有效的括号 + 下一个更大的元素

1、栈结构

和队列相反，栈先进后出

时间复杂度：访问、插入、删除都在栈顶进行操作，时间复杂度为O(1)，搜索需要遍历，为O(n)

2、Java中的栈

Stack类，继承关系：

常用操作与时间复杂度：

3、leetcode20：有效的括号

解法思路：拿到字符串后，遍历，如果是左括号，则入栈，如果是右括号，则弹栈出来一个左括号。遍历完后，栈里有数据，说明左括号多了，不合规。中途出现栈里弹不出左括号的，说明右括号多了，也不合规。

代码实现：

public class P20 {

    public static boolean checkStr(String str) {
        if (str.length() == 0 || null == str) {
            return true;
        }
        //初始化一个栈
        Stack<String> stack = new Stack<>();
        String[] array = str.split("");
        for (String s : array) {
            //入栈左括号
            if ("(".equals(s) || "{".equals(s) || "[".equals(s)) {
                stack.push(s);
            } else {
                // 必须先左后右
                if (stack.size() == 0){
                    return false;
                } else {
                    // 入栈的是右括号，且之前栈里有左括号了，那就取栈顶
                    String temp = stack.pop();
                    // 如果是右圆括号，那栈帧必须是左圆括号，否则就是([)之类的
                    if (")".equals(s)) {
                        if (!"(".equals(temp)) {
                            return false;
                        }
                    }
                    if ("}".equals(s)) {
                        if (!"{".equals(temp)) {
                            return false;
                        }
                    }
                    if ("]".equals(s)) {
                        if (!"[".equals(temp)) {
                            return false;
                        }
                    }
                }
            }
        }
        return stack.isEmpty();
    }
}

测试：

public class P20 {
    public static void main(String[] args) {
        String str = "{}({[]})";
        System.out.println(checkStr(str));
    }
}

4、leetcode496：下一个更大元素

num1数组中有个4，在num2中找到4，其后面只有个2，没有比4更大的了，返回-1

根据这个特点：比较的是该元素在num2位置后面的元素有没有比该元素大的，如果采用栈，将num2入栈，遍历num1的每个元素n，每次弹出栈顶元素来比较，循环直到取到和元素n相等的值或者栈空时停止循环，如果一直没有取到更大的值，则返回-1。期间如果中途取到了更大的值，则存一下，以防有多个更大的值，下次出现更大的值，不论大小，直接覆盖，因为取的是下一个更大元素，不是下一个更大的元素里的最大的元素。每这样对比完num1的一个元素，就将结果写入要return的结果数组中。

每循环一次，处理num1的一个元素，num2的栈元素也会被弹出，等处理num1的下一个元素时，num2的栈就不完整了，因此，这里用一个tmp临时栈，记录num2栈被弹出的元素，后面再塞回num2栈，以便处理num1的下一个元素。

public class P496 {

    /**
     *
     * num1是num2的子集
     */
    public static int[] getNextMore (int[] num1, int[] num2) {
        // num1不是num2的子集，直接返回空
        if (num1 == null || num2 == null || num1.length > num2.length) {
            return null;
        }
        // num2数组转为栈
        Stack<Integer> stack = new Stack<>();
        for (int i : num2) {
            stack.push(i);
        }
        // 创建一个初始化数组存结果集
        int[] result = new int[num1.length];
        // 创建一个临时栈，存每轮找数被弹出来的num2的元素，一轮完成后，再从临时栈塞回num2的栈
        Stack<Integer> tempStack = new Stack<>();
        // 这里不用foreach，要用下标i存入结果集的对应位置
        for (int i = 0; i < num1.length; i++) {
            // 下一个更大值，默认-1，找到更大的了就覆盖
            int tempMore = -1 ;
            while (true) {
                Integer top = stack.pop();
                tempStack.push(top);
                if (top == num1[i] || stack.isEmpty()){
                    // 找到了或者num2栈弹完了
                    break;
                } else if (top > num1[i]) {
                    tempMore = top;
                }
            }
            // 找到了num1的一个元素的更大的值
            result[i] = tempMore;
            // 获取到某个元素的下一个更大值后，把弹栈的数据再塞回去，准备下一轮循环再处理num1的下一个元素了
            while (!tempStack.isEmpty()) {
                stack.push(tempStack.pop());
            }
        }
        return result;
    }
}

测试：

public class P496 {
    public static void main(String[] args) {
        int[] num1 = {4, 1, 2};
        int[] num2 = {1, 3, 4, 2};
        for (int i : getNextMore(num1, num2)) {
            System.out.print(i + " ");
        }
    }
}