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 + " ");
        }
    }
}

在这里插入图片描述

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部