剑指offer（20）——C++实现包含min函数的栈

秒速五厘米 2024-04-17 05:43 11阅读 0赞

# 题目 #

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

# 考察点 #

*  栈

# 解题思路 #

首先要保证它始终是一个栈的结构，首先要保证它始终是一个栈的结构，即弹出的始终是栈顶元素。那么这个时候就要使用辅助栈来完成存储和更新最小栈的作用，即每次压入的元素都是当前原来栈中的最小数。

# 完整代码 #

/*20-包含min函数的栈 */
    #include<iostream>
    #include<stack>
    using namespace std;
    
    class Solution {
        
    public:
    	void push(int value) {
        
    		sdata.push(value);//将数据压入栈中
    
    		//同时辅助栈中压入数据，并保持栈顶始终未最小值
    		if (smin.empty() || value < smin.top())
    			smin.push(value);
    		else
    			smin.push(smin.top());
    	}
    	void pop() {
        
    		
    		//if (smin.top() == sdata.top())
    		smin.pop();
    		sdata.pop();
    	}
    	int top() {
        
    		return sdata.top();
    	}
    	int min() {
        
    		return smin.top();
    	}
    private:
    	stack<int> sdata;
    	stack<int> smin;
    };
    int main()
    {
        
    	Solution s;
    	
    	//stack<int> data;
    	for (int i = 0; i < 5; i++)
    		s.push(i);
    	cout << s.min() << endl;
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关剑指offer（20）——C++实现包含min函数的栈

题目定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。考察点 * 栈解题思路首先要保证...

秒速五厘米/ 2024年04月17日 05:43/ 0 赞/ 12 阅读

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

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

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

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

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

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

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

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O(1)）。时间限制：1秒；空间限制：32768K；本题知识点：栈

忘是亡心i/ 2022年05月05日 05:58/ 0 赞/ 171 阅读

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

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

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

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

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

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

相关剑指offer-包含min函数的栈（C++）

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。实现思想利用两个栈来实现，栈1用来当普通栈使用

男娘i/ 2022年02月04日 16:13/ 0 赞/ 113 阅读

相关【剑指offer】包含min函数的栈，C++实现

[博客文章索引地址][Link 1] [博客文章中代码的github地址][github] 1.题目定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的mi

骑猪看日落/ 2021年12月17日 13:49/ 0 赞/ 59 阅读

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

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

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

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

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

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