从C语言到C++_18(stack和queue的常用函数+相关练习)力扣(中)

简介: 从C语言到C++_18(stack和queue的常用函数+相关练习)力扣

从C语言到C++_18(stack和queue的常用函数+相关练习)力扣(上):https://developer.aliyun.com/article/1521375

4. 栈和队列的相关OJ

155. 最小栈 - 力扣(LeetCode)

难度中等

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

实现 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.

提示:

  • -2^31 <= val <= 2^31 - 1
  • poptopgetMin 操作总是在 非空栈 上调用
  • push, pop, top, and getMin最多被调用 3 * 10^4
class MinStack {
public:
    MinStack() {
 
    }
    
    void push(int val) {
 
    }
    
    void pop() {
 
    }
    
    int top() {
 
    }
    
    int getMin() {
 
    }
};
 
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

解析代码:

思路:使用一个辅助栈,与元素栈同步插入与删除,用于存储与每个元素对应的最小值。

当一个元素要入栈时,我们取当前辅助栈的栈顶存储的最小值,

与当前元素比较得出最小值将这个最小值插入辅助栈中;

当一个元素要出栈时,我们把辅助栈的栈顶一样元素也一并弹出;

在任意一个时刻,栈内元素的最小值就存储在辅助栈的栈顶元素中。

给个图理解理解:

class MinStack {
public:
    MinStack() { // 构造函数不用写,删掉也行
 
    }
    
    void push(int val) {
        _st.push(val);
        if(_minst.empty() || val <= _minst.top())//要先判空
        {
            _minst.push(val);//栈空或者值小于等于栈顶元素才入栈
        }
    }
    
    void pop() {
        if(_st.top() == _minst.top())
        {        //题目说栈空 不会调用pop,top和getMin,所以不判空也行
            _minst.pop();//两个栈元素相等就_minst.pop
        }
        _st.pop();//要先判断_minst要不要pop
    }
    
    int top() {
        return _st.top();
    }
    
    int getMin() {
        return _minst.top();
    }
private:
    stack<int> _st;// 一个栈完成常规接口
    stack<int> _minst; // 一个栈完成getMin
};
 
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

拓展:如果面试的时候问到这题,面试官问你如果要插入的元素中包含大量的重复数据的话,

比如100万个1,中间包含不一样的数,要怎么优化呢?

这就考察到引用计数了。我们的辅助栈可以存一个结构体一个存值,一个计数:

可以去写写,面试时也不一定要写,可能就是讲思路,主要是考察思维或不活跃。

剑指 Offer 31. 栈的压入、弹出序列 - 力扣(LeetCode)

946. 验证栈序列 - 力扣(LeetCode)

栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

ps(上面三题是一模一样的,血赚两题)

难度中等

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。

假设压入栈的所有数字均不相等。例如,序列 {1,2,3,4,5} 是某栈的压栈序列,

序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列,

但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

示例 1:

输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]

输出:true

解释:我们可以按以下顺序执行:

push(1), push(2), push(3), push(4), pop() -> 4,

push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

示例 2:

输入:pushed = [1,2,3,4,5], popped = [4,3,5,1,2]

输出:false

解释:1 不能在 2 之前弹出。

提示:

  1. 0 <= pushed.length == popped.length <= 1000
  2. 0 <= pushed[i], popped[i] < 1000
  3. pushedpopped 的排列。
class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
 
    }
};

解析代码:

遍历两个数组,模拟入栈和出栈操作,判断两个数组是否为有效的栈操作序列。

不求同年同月同日入栈,但求同年同月同日出栈:

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        if (pushed.size() != popped.size())
        {
            return false;
        }
        stack<int> st;
        int popi = 0;//出栈序列的下标
        for (const auto& e : pushed)//遍历入栈序列
        {
            st.push(e);//不匹配就持续入,匹配就持续出
            while (!st.empty() && st.top() == popped[popi])
            {
                st.pop();//一样的话就出栈,++popi
                ++popi;
            }
        }
        //return popi == popped.size();//出栈序列全部匹配->true
        return st.empty();//st为空->true
    }
};

牛客代码:

class Solution {
public:
    bool IsPopOrder(vector<int> pushV,vector<int> popV) {
        if (pushV.size() != popV.size())
    {
      return false;
    }
        stack<int> st;
        int popi = 0;
        for(const auto& e : pushV)
        {
            st.push(e);
            while(!st.empty() && st.top() == popV[popi])
            {
                st.pop();
                ++popi;
            }
        }
        return st.empty();
    }
};

从C语言到C++_18(stack和queue的常用函数+相关练习)力扣(下):https://developer.aliyun.com/article/1521384


目录
相关文章
|
2天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
2天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
3天前
|
C语言 C++ 编译器
【C++语言】冲突-C语言:输入输出、缺省参数、引用、内联函数
【C++语言】冲突-C语言:输入输出、缺省参数、引用、内联函数
【C++语言】冲突-C语言:输入输出、缺省参数、引用、内联函数
|
3天前
|
C语言 C++
【C++语言】冲突-C语言:命名空间
【C++语言】冲突-C语言:命名空间
|
3天前
|
C语言 C++
【数据结构】C语言实现:栈(Stack)与队列(Queue)
【数据结构】C语言实现:栈(Stack)与队列(Queue)
|
11天前
|
程序员 C语言 C++
C语言学习记录——动态内存习题(经典的笔试题)、C/C++中程序内存区域划分
C语言学习记录——动态内存习题(经典的笔试题)、C/C++中程序内存区域划分
10 0
|
11天前
|
C语言 C++ 容器
【C++初阶学习】第十二弹——stack和queue的介绍和使用
【C++初阶学习】第十二弹——stack和queue的介绍和使用
20 8
|
19天前
|
安全 Linux 编译器
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)(下)
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)
22 0
|
4天前
|
算法 Unix Linux
C语言随机数的产生(rand、srand、time函数细节讲解)
C语言随机数的产生(rand、srand、time函数细节讲解)
|
2天前
|
安全 C语言
【C语言基础】:内存操作函数
【C语言基础】:内存操作函数

热门文章

最新文章