目录

1. 最小栈

题目描述

解题思路

参考答案

2.栈的压入、弹出序列

题目描述

解题思路

参考答案

3.二叉树的层序遍历

题目描述

解题思路

参考答案

---

1. 最小栈

最小栈https://leetcode.cn/problems/min-stack/

题目描述

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

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

• -231 <= val <= 231 - 1
• pop、top 和 getMin 操作总是在 非空栈 上调用
• push, pop, top, and getMin最多被调用 3 * 104 次

解题思路

        本题可以通过两个stack栈：s和s_min。
        s当做普通的栈来存储每一个数据。
        s_min用来存储第一个元素和之后每一个比s_min栈顶元素小的元素（包括相等的数据），插入数据的过程随着s的push过程一同进行。此时s_min的栈顶数据就是最小元素。
        通过这个方法就可以实现“常数时间内检索到最小元素”。
        在s删除数据的时候，若是s_min的栈顶元素和要删除的数据相等时，则删除该栈顶元素。

参考答案

class MinStack
{
    /*
        本题可以通过两个stack栈：s和s_min
        s当做普通的栈来存储每一个数据
        s_min用来存储第一个元素和之后每一个比s_min栈顶元素
    小的元素（包括相等的数据），插入数据的过程随着s的push过程
    一同进行。此时s_min的栈顶数据就是最小元素。
        通过这个方法就可以实现“常数时间内检索到最小元素”
        在s删除数据的时候，若是s_min的栈顶元素和要删除的数据
    相等时，则删除该栈顶元素。
    */

public:
    MinStack()
    {}

    void push(int val)
    {
        //第一个元素先放在s_min中
        if (s.empty())
            s_min.push(val);

        s.push(val);

        //随后的每一个比s_min栈顶元素小或者相等的数据也都push到s_min上
        if (val <= s_min.top())
            s_min.push(val);
    }

    void pop()
    {
        //若是s和s_min的栈顶数据相等时，删除s_min的栈顶元素
        if (s.top() == s_min.top())
            s_min.pop();

        s.pop();
    }

    int top()
    {
        return s.top();
    }

    int getMin()
    {
        return s_min.top();
    }

private:
    //这里注意要加模版参数<int>
    stack<int> s;
    stack<int> s_min;
};

2.栈的压入、弹出序列

栈的压入、弹出序列https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&tqId=23290&sourceUrl=

题目描述

描述

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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

输入：[1,2,3,4,5],[4,5,3,2,1]

返回值：true

说明：可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop() 这样的顺序得到[4,5,3,2,1]这个序列，返回true

示例2

输入：[1,2,3,4,5],[4,3,5,1,2]

返回值：false

说明：由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false

解题思路

    解题思路：模拟出栈过程
    定义一个栈，数据按照入栈顺序依次入栈。
    定义一个下标index指向出栈的第一个元素。
    出栈条件：当入栈元素和下标index指向的出栈元素相同时。
    当满足出栈条件时，将栈中顶部元素出栈，下标自加一，之后持续进行出栈操作，直到栈为空或者不满足出栈条件，之后继续进行入栈操作。
    当所有元素都入栈完成后，若给出的“栈的压入、弹出序列”正确的话，此时栈为空，返回true；否则返回false
 

参考答案

/*
    解题思路：模拟出栈过程
    定义一个栈，数据按照入栈顺序依次入栈。
    定义一个下标index指向出栈的第一个元素。
    出栈条件：当入栈元素和下标index指向的出栈元素相同时。
    当满足出栈条件时，将栈中顶部元素出栈，下标自加一，之后持续进行出栈操作，直到栈为空或者不满足出栈条件，之后继续进行入栈操作。
    当所有元素都入栈完成后，若给出的“栈的压入、弹出序列”正确的话，此时栈为空，返回true；否则返回false

*/

class Solution
{
public:
    bool IsPopOrder(vector<int>& pushV, vector<int>& popV)
    {
        stack<int> s;
        int index = 0;
        auto it = pushV.begin();
        while (it != pushV.end())
        {
            s.push(*it);
            it++;
            while (!s.empty() && s.top() == popV[index])
            {
                s.pop();
                index++;
            }
        }

        if (s.empty())
            return true;
        else
            return false;
    }
};

3.二叉树的层序遍历

二叉树的层序遍历https://leetcode.cn/problems/binary-tree-level-order-traversal/

题目描述

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

• 树中节点数目在范围 [0, 2000] 内
• -1000 <= Node.val <= 1000

解题思路

 解题思路：
    创建一个队列，依次储存每个节点的左节点和右节点。
    定义一个size，用来记录每一层有多少的元素。
    每次将队列最开始的元素的左节点和右节点push入队列，并将这个元素的数据加到vector数组v上，然后pop掉这个元素……如此重复size次，就将每一层的数据记录了到数组v中，将数组v加到二维数组vv上，之后再更新size值，直到队列为空，则层序遍历结束。

参考答案

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

/*
    解题思路：
    创建一个队列，依次储存每个节点的左节点和右节点。
    定义一个size，又来记录每一层有多少的元素。
    每次将队列最开始的元素的左节点和右节点push入队列，并将这个元素的数据加到vector数组v上，然后pop掉这个元素……如此重复size次，就将每一层的数据记录了到数组v中，将数组v加到二维数组vv上，之后再更新size值，直到队列为空，则层序遍历结束。
*/

class Solution 
{
public:
    vector<vector<int>> levelOrder(TreeNode* root) 
    {
        vector<vector<int>> vv;

        //二叉树为空时直接返回
        if(root==nullptr)
            return vv;

        queue<TreeNode*> q;
        int size=1; //二叉树不为空时，则至少有一个头节点，该节点为第一层，数据个数为1
        q.push(root);
        while(!q.empty())
        {
            vector<int> v;

            while(size--)
            {
                TreeNode* front=q.front();//记录队列中的第一个元素（最先入队列的数据）

                //若有左节点和右节点，则分别将其入队列
                if(front->left)
                    q.push(front->left);
                if(front->right)
                    q.push(front->right);
                //将第一个数据记录到数组中
                v.push_back(front->val);
                //将第一个数据从队列中删除
                q.pop();
            }

            vv.push_back(v);
            size=q.size(); //更新size
        }
        return vv;
    }
};