「算法刷题」栈相关的LeetCode题目实现

[TOC]

一、设计最小栈

剑指 Offer 30. 包含min函数的栈（中等函数）

155. 最小栈（简单难度）

面试题 03.02. 栈的最小值（简单难度）

class MinStack {
public:
    stack<int> stack1;//正常栈，实现栈的正常功能
    stack<int> stack2;//辅助栈，负责实现min函数，入栈时只入比自己栈顶元素小的元素，出栈时和当前元素相等就出栈
    MinStack() {}
    // 入栈
    void push(int val) {
        stack1.push(val);//正常入栈
        // 如果辅助栈为空或者辅助栈栈顶元素比较大，就入栈
        if(stack2.empty()||stack2.top()>=val)stack2.push(val);
    }
    // 出栈
    void pop() {
        int top=stack1.top();
        stack1.pop();// 正常出栈
        // 如果出栈的元素和辅助栈栈顶元素相等
        if(top==stack2.top()) stack2.pop();
    }
    // 获取栈顶元素
    int top() {
        return stack1.top();//正常的栈顶元素
    }
    // 获取最小值
    int getMin() {
        return stack2.top();//辅助栈的栈顶元素
    }
};

二、验证栈序列

剑指 Offer 31. 栈的压入、弹出序列

946. 验证栈序列（中等难度）

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack<int> stk;
        int i=0;
        for(int x:pushed){
            stk.push(x);
            // 循环检查，如果栈顶元素和出栈队列元素相同就出栈
            // 栈内元素用完就继续加
            while(!stk.empty()&&stk.top()==popped[i]){
                stk.pop();
                i++;
            }
        }
        return stk.empty();
    }
};