剑指offer 包含min函数的栈

系统管理员 2021-11-02 05:04 315阅读 0赞

# [剑指offer题型分类及各题的代码及解题思路][offer] #

## 题目描述 ##

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

结构定义如下：

class Solution {
    public:
        void push(int value) {
            
        }
        void pop() {
            
        }
        int top() {
            
        }
        int min() {
            
        }
    };

思路：利用一个辅助栈来存放最小值（来自剑指offer第二版 P165）

栈        stack1: 3，4，2，5，1

辅助栈 stack2: 3，3，2，2，1

每入栈一次，就与辅助栈顶比较大小，

如果小就入栈，如果大就入栈当前的辅助栈顶

当出栈时，辅助栈也要出栈；

这种做法可以保证辅助栈顶一定是当前栈的最小值。

C++实现代码如下：

stack<int> stack1,stack2;
    //入栈操作
    void push(int value)
    {
    	stack1.push(value);
    	if(stack2.empty() || value < stack2.top())
    	{
    		stack2.push(value);
    	}
    	else
    	{
    		stack2.push(stack2.top());
    	}
    }
    //出栈操作
    void pop() 
    {
    	stack1.pop();
    	stack2.pop();
    }
    //取栈顶元素操作
    int top() 
    {
    	return stack1.top();
    }
    //取栈中最小元素操作
    int min() 
    {
    	return stack2.top();
    }

[offer]: https://blog.csdn.net/qq_26079093/article/details/96605538

发表评论取消回复

表情：

评论列表（有 0 条评论，315人围观）

还没有评论，来说两句吧...

相关阅读

相关剑指offer——包含min函数的栈

![转自leetcode剑指offer][leetcode_offer]思路：使用两个栈，栈A，栈B，栈A用于存储正常的值，栈B存储最小的元素，插入时，栈A直接插入元素到栈顶，

桃扇骨/ 2023年01月20日 08:08/ 0 赞/ 25 阅读

相关剑指offer——包含min函数的栈

题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。分析：定义一个辅助栈，保存对应元素存在时当前栈中的最小元素，即可在O(1)的时间内找到最小的

叁歲伎倆/ 2022年05月31日 12:50/ 0 赞/ 194 阅读

相关剑指Offer-包含min函数的栈

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。基本思路：利用两个栈，一个数据栈，一个辅助栈（保存当前栈中数据的最小值）数据栈和辅

古城微笑少年丶/ 2022年05月23日 01:17/ 0 赞/ 183 阅读

相关剑指Offer | 包含min函数的栈

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

你的名字/ 2022年05月23日 00:35/ 0 赞/ 193 阅读

相关剑指offer:包含min函数的栈

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。 AC C++ Solution: 使用两个栈,一个栈

缺乏、安全感/ 2022年04月10日 07:58/ 0 赞/ 220 阅读

相关【剑指offer】包含min函数的栈

包含min函数的栈题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。 AC代码思路：用一个

痛定思痛。/ 2022年04月02日 15:52/ 0 赞/ 190 阅读

相关剑指Offer-包含min函数的栈

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数 (时间复杂度应为O(1))。看到题目特别是模拟编辑器上的代码，给了四个空函数，一

「爱情、让人受尽委屈。」/ 2022年02月27日 11:56/ 0 赞/ 214 阅读

相关剑指Offer——包含min函数的栈

1、题目描述　　定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。 2、代码实现 package com.b

梦里梦外;/ 2021年12月04日 05:07/ 0 赞/ 265 阅读

相关剑指offer 包含min函数的栈

[剑指offer题型分类及各题的代码及解题思路][offer] 题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为

系统管理员/ 2021年11月02日 05:04/ 0 赞/ 316 阅读

相关剑指offer：包含min函数的栈

试题：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。代码：为了实现栈的功能，我们可以简单的利用java

ゞ浴缸里的玫瑰/ 2021年06月24日 16:09/ 0 赞/ 358 阅读