【一刷《剑指Offer》】面试题 21:包含 main 函数的栈

简介: 【一刷《剑指Offer》】面试题 21:包含 main 函数的栈

力扣对应题目链接:155. 最小栈 - 力扣(LeetCode)

牛客对应题目链接:包含min函数的栈_牛客题霸_牛客网 (nowcoder.com)

核心考点 :栈的规则性设计。


一、《剑指Offer》对应内容


二、分析题目

很容易想到,在栈内部保存 min 变量,每次更新的时候,都对 min 变量进行更新。但是,面试官很容易就会问到:如果想拿出第二小,第三小的值怎么拿?

这时再用上面的办法就不行了。为了满足通用,我们使用一个辅助栈,内部保存元素的个数和数据栈完全一样。不过,辅助栈内部永远保存本次入栈的数为所有数据的最小值

注意辅助栈内部元素可能会出现 “必要性重复

这里是为了实现算法, 所以就不从 0 开始实现 stack 了。题面说了,保证测试中不会当栈为空的时候,对栈调用 pop() 或者 min() 或者 top() 方法。所以,后面的代码对空的检验可有可无。


三、代码

//力扣
class MinStack {
private:
    stack<int> val_stack;
    stack<int> min_stack;
public:
    MinStack() {}
    
    void push(int val) {
        val_stack.push(val);
        if(min_stack.empty() || val<min_stack.top())
            min_stack.push(val);
        else
            min_stack.push(min_stack.top());
    }
    
    void pop() {
        if(val_stack.empty() || min_stack.empty()) return;
        val_stack.pop();
        min_stack.pop();
    }
    
    int top() {
        return val_stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
};
 
/**
 * 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 Solution {
private:
    stack<int> val_stack;
    stack<int> min_stack;
public:
    void push(int value) {
        val_stack.push(value);
        if(min_stack.empty() || value<min_stack.top())
            min_stack.push(value);
        else
            min_stack.push(min_stack.top());
    }
    void pop() {
        val_stack.pop();
        min_stack.pop();
    }
    int top() {
        return val_stack.top();
    }
    int min() {
        return min_stack.top();
    }
};


相关文章
|
2天前
|
安全 Android开发 Kotlin
Android经典面试题之Kotlin中常见作用域函数
**Kotlin作用域函数概览**: `let`, `run`, `with`, `apply`, `also`. `let`安全调用并返回结果; `run`在上下文中执行代码并返回结果; `with`执行代码块,返回结果; `apply`配置对象后返回自身; `also`附加操作后返回自身
17 8
|
13天前
|
Android开发 Kotlin
Android面试题之kotlin中怎么限制一个函数参数的取值范围和取值类型等
在Kotlin中,限制函数参数可通过类型系统、泛型、条件检查、数据类、密封类和注解实现。例如,使用枚举限制参数为特定值,泛型约束确保参数为Number子类,条件检查如`require`确保参数在特定范围内,数据类封装可添加验证,密封类限制为一组预定义值,注解结合第三方库如Bean Validation进行校验。
25 6
|
15天前
|
存储 安全 Java
Java面试题:在JVM中,堆和栈有什么区别?请详细解释说明,要深入到底层知识
Java面试题:在JVM中,堆和栈有什么区别?请详细解释说明,要深入到底层知识
28 3
|
15天前
|
存储 缓存 监控
Java面试题:解释堆和栈的OutOfMemoryError通常在什么情况下会发生
Java面试题:解释堆和栈的OutOfMemoryError通常在什么情况下会发生
20 3
|
15天前
|
存储 设计模式 监控
Java面试题:简述JVM的内存结构,包括堆、栈、方法区等。栈内存优化的方法有 哪些?
Java面试题:简述JVM的内存结构,包括堆、栈、方法区等。栈内存优化的方法有 哪些?
21 0
|
15天前
|
Java 开发者
Java面试题:Java内存管理精要与多线程协同策略,Java内存管理:堆内存、栈内存、方法区、垃圾收集机制等,多线程编程的掌握,包括线程创建、同步机制的原理
Java面试题:Java内存管理精要与多线程协同策略,Java内存管理:堆内存、栈内存、方法区、垃圾收集机制等,多线程编程的掌握,包括线程创建、同步机制的原理
17 0
|
15天前
|
算法 Java 开发者
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
Java面试题:Java内存探秘与多线程并发实战,Java内存模型及分区:理解Java堆、栈、方法区等内存区域的作用,垃圾收集机制:掌握常见的垃圾收集算法及其优缺点
16 0
|
3天前
|
SQL Java Unix
Android经典面试题之Java中获取时间戳的方式有哪些?有什么区别?
在Java中获取时间戳有多种方式,包括`System.currentTimeMillis()`(毫秒级,适用于日志和计时)、`System.nanoTime()`(纳秒级,高精度计时)、`Instant.now().toEpochMilli()`(毫秒级,ISO-8601标准)和`Instant.now().getEpochSecond()`(秒级)。`Timestamp.valueOf(LocalDateTime.now()).getTime()`适用于数据库操作。选择方法取决于精度、用途和时间起点的需求。
17 3
|
20天前
|
存储 算法 Java
Java面试之SpringCloud篇
Java面试之SpringCloud篇
35 1
|
20天前
|
SQL 关系型数据库 MySQL
java面试之MySQL数据库篇
java面试之MySQL数据库篇
24 0
java面试之MySQL数据库篇