【迎战蓝桥】 算法·每日一题（今日详解）-- day6

【大家好，我是爱干饭的猿，如果喜欢这篇文章，点个赞👍，关注一下吧，后续会一直分享题目与算法思路】

🌳1. 包含min函数的栈

描述

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

此栈包含的方法有：

push(value):将value压入栈中

pop():弹出栈顶元素

top():获取栈顶元素

min():获取栈中最小元素

解题思路：

🎈1. 思路一：看到题目时，我们可以简单的想到设置一个min变量储存最小值，每当入数据栈元素小于min时，更新min即可。

🎈2. 思路二：但是思路一我们只能得到数据栈中的最小值，假若面试官要求我们求数据栈中第二小值和第三小值，此方法就行不通了。因此我们可以设置一个辅助栈，辅助栈中的元素个数和数据栈个数相同，只是辅助栈每次存入的是当前已存入数据栈中的最小值，这样如果要求数据栈中第二小值，可以同时让数据栈data_stack和辅助栈min_stack先出栈一个元素，然后return min_stack.peek即可得到数据栈中第二小的值。

🍤思路二：代码如下：

import java.util.Stack;
public class TwoStackIncludeMin_17 {
    // 数据栈（存入栈元素）
    Stack<Integer> data_stack = new Stack<>();
    // 辅助栈（存入当前数据栈中元素最小值）
    Stack<Integer> min_stack = new Stack<>();
    
    public void push(int node) {
        // 先将node存入数据栈
        data_stack.push(node);
        
        // 判断辅助栈是否为空
        if(min_stack.isEmpty()){
            // 如果辅助栈为空，直接将node存入辅助栈
            min_stack.push(node);
        }else {
            // 如果辅助栈不为空，先将node和辅助栈的栈顶元素做比较
            // 将小的元素存入辅助栈
            if(min_stack.peek() <= node){
                // 辅助栈的栈顶元素更小
                min_stack.push(min_stack.peek());
            }else {
                // node 更小
                min_stack.push(node);
            }
        }
    }

    public void pop() {
        // 数据栈和辅助栈同时出栈，保证两栈元素个数一致
        data_stack.pop();
        min_stack.pop();
    }

    public int top() {
        return data_stack.peek();
    }

    // 当期数据栈中最小元素就是辅助栈的栈顶元素
    public int min() {
        return min_stack.peek();
    }
}

🌳2. 栈的压入、弹出序列

描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1. 0<=pushV.length == popV.length <=1000

2. -1000<=pushV[i]<=1000

3. pushV 的所有数字均不相同

解题思路：

🎈1. 思路一：我们知道可以根据第二个序列也就是出栈顺序，能够得到指定的入栈顺序

（如例题中，第二个序列第一个数为4，入栈时肯定先入栈1，2，3，4，然后才能将4出栈；第二个序列第二个数为5，所以入栈时再将5入栈，然后才能将5出栈，继而将3出栈，2出栈，1出栈）

因此，我们可以遍历第一个序列和第二个序列，当第二个序列元素不等于入栈元素时，继续将第一个序列元素入栈；当第二个序列元素等于入栈元素时，弹出栈顶元素；

如此一直循环，当第一个序列元素全部入栈后，退出循环，判断此时栈是否为空，如果栈为空，说明第二个序列元素将栈中元素全部弹出，第二个序列就是是为该栈的弹出顺序。

🍤思路一：代码如下：

import java.util.Stack;
public class IsPopOrder_18 {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        // 当第一序列或第二序列为空时，直接返回false
        if(pushA == null || popA == null || pushA.length ==0 || popA.length == 0){
            return false;
        }

        Stack<Integer> stack = new Stack<>();
        int i = 0;
        int j = 0;
        for (;i < pushA.length ; i++) {
            // 将第一序列元素入栈
            stack.push(pushA[i]);
            // 当第二个序列元素等于入栈元素时，弹出栈顶元素
            while (!stack.isEmpty() && stack.peek() == popA[j]){
                stack.pop();
                j++;
            }
        }
        // 如果符合要求，最后栈结构一定是空的
        return stack.isEmpty();
    }
}

🌳3. 从上往下打印二叉树

描述

不分行从上往下打印出二叉树的每个节点，同层节点从左至右打印。例如输入{8,6,10,#,#,2,1}，如以下图中的示例二叉树，则依次打印8,6,10,2,1(空节点不打印，跳过)，请你将打印的结果存放到一个数组里面。

解题思路：

🎈1. 思路一：本质是层序遍历二叉树，借助队列queue完成。先将根节点存入队列中，然后进入while循环，将队首元素出队并存入list数组中，然后将该队首节点右孩子入队，再将该队首节点左孩子入队。当队列为空时退出循环，list数组中即层序遍历结果。

🍤思路一：代码如下：

public class PrintFromTopToBottom_19 {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        // 创建list数组
        ArrayList<Integer> list = new ArrayList<>();
        // 创建queue队列
        Queue<TreeNode> queue = new LinkedList<>();

        // 先将根节点入队
        queue.offer(root);
        // 当队列不为空时
        while (!queue.isEmpty()){
            // 队首元素出队并存入list数组中
            TreeNode node = queue.poll();
            list.add(node.val);

            if(node.left != null){
                // 将该队首节点右孩子入队
                queue.offer(node.left);
            }
            if(node.right != null){
                // 将该队首节点左孩子入队
                queue.offer(node.right);
            }
        }
        return list;
    }
}

🌳4. 二叉搜索树的后序遍历序列

描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。

提示：

1.二叉搜索树是指父亲节点大于左子树中的全部节点，但是小于右子树中的全部节点的树。

2.该题我们约定空树不是二叉搜索树

3.后序遍历是指按照 “左子树-右子树-根节点” 的顺序遍历

4.参考下面的二叉搜索树，示例 1

解题思路：

🎈1. 思路一：首先我们应该知道，二叉搜索树性质：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。

后序遍历：左右根方式遍历

所以我们判断依据如下：二叉搜索树
BST的后序序列的合法序列是：对于一个序列S，最后一个元素是x （也就是root节点），如果去掉最后一个元素x的序列为 T，那么T满足：T可以分成两段，前一段（x的左子树）节点值都小于x，后一段（x的右子树）节点值大于x，且这两段（子树）都是合法的后序序列 ；当后一段（x的
右子树）出现节点小于x时，说明不是合法的后序序列，return false 即可。

🍤思路一：代码如下：

public class VerifySquenceOfBST_20 {
    public boolean VerifySquenceOfBST(int [] sequence) {
        // 序列为空时，直接return false
        if(sequence == null || sequence.length == 0){
            return false;
        }

        return VerifySquenceOfBSTHelper(sequence,0,sequence.length-1);
    }

    private boolean VerifySquenceOfBSTHelper(int[] sequence, int start, int end) {
        // 当子序列首索引大于等于尾索引，说明子序列都是合法后序序列，判断完毕，return true
        if(start >= end){
            return true;
        }
        // 得到当前子序列首索引
        int i = start;
        // 找到子序列中后一段（x的右子树）第一个大于root节点的位置
        while(i < end && sequence[i] < sequence[end]){
            i++;
        }
        // 遍历子序列中后一段（x的右子树）节点
        for (int j = i; j < end; j++) {
            // 当后一段（x的右子树）出现节点小于x时，说明不是合法的后序序列，return false
            if(sequence[j] < sequence[end]){
                return false;
            }
        }
        // 递归判断当前序列的前一段和后一段是否是合法的后序序列
        return VerifySquenceOfBSTHelper(sequence,start,i-1) && VerifySquenceOfBSTHelper(sequence,i,end-1);
    }
}