题目描述

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

牛客网题目链接

解题思路

构造一个和栈容量一致缓存栈，用于存储存储当前栈的最小值，具体操作过程为：

入栈时数据直接入栈，缓存栈则入当前的最小值出栈时数据栈和缓存栈都出栈

代码实现

使用栈的版本

class Solution { public: void push(int value) { data.push(value); if(cahe.empty()||cahe.top()>value)cahe.push(value); else cahe.push(cahe.top()); } void pop() { if(!data.empty())data.pop(),cahe.pop(); } int top() { if(!data.empty())return data.top(); } int min() { if(!cahe.empty())return cahe.top(); } private: stack <int> data,cahe; }; 运行时间：3ms 占用内存：484k

使用数组的版本

using namespace std; class Solution { public: void push(int value) { data.push_back(value); if(cahe.empty()||cahe[cahe.size()-1]>value)cahe.push_back(value); else cahe.push_back(cahe[cahe.size()-1]); } void pop() { if(!data.empty())data.pop_back(),cahe.pop_back(); } int top() { if(!data.empty())return data[data.size()-1]; } int min() { if(!cahe.empty())return cahe[cahe.size()-1]; } private: vector <int> data,cahe; }; 运行时间：2ms 占用内存：376k