首页 > 代码库 > 用O(1)的时间复杂度，找到栈和队列中的最小（大）值
用O(1)的时间复杂度，找到栈和队列中的最小（大）值
最近刷剑指offer，看到两道编程题，考察在O（1）的复杂度内，找出最值。
觉得很有意思，很有借鉴意义，故记录在此。
需要注意的是，这里所说的O(1) 有个前提， 就是已经通过某种容器的存储方式进行初始化，
不然不可能在还未遍历数据的情况下就定位出最值。
问题1： 重新定义栈的数据结构，实现一个能够在O(1)时间复杂度内求出栈内最小元素的min函数。
思路： 需要一个变量minimum保存目前栈内所有值的最小值，因为最小值是随着出栈，入栈操作变化的，所以一个变量是不够的。
考虑引入辅助栈，辅助栈中保存于数据栈中同步的当前最小值。 即辅助栈栈顶元素为当前数据栈内的最小值。
例如：stack_data中元素为[3,4,1,2] , 则stack_support中为[3,3,1,1]。 当数据栈2出栈，同时辅助栈1出栈， 则剩余中最小值还是辅助栈顶元素1； 数据栈再出栈1，辅助栈也出栈1， 则剩下的数据栈最小元素为辅助栈栈顶元素3.
需要重写栈的push， pop操作。
C++代码：
1 template <typename T> class NewStack 2 { 3 private : 4 std::stack<T> stack_data; 5 std::stack<T> stack_support; 6 7 8 public: 9 10 NewStack();11 ~NewStack();12 13 void push( T value)14 {15 stack_data.push_back(value);16 17 if (stack_support.size()==0 || stack_support.top()>value)18 stack_support.push_back(value);19 else:20 stack_support.push_back(stack_support.top());21 22 }23 24 void pop()25 {26 if (stack_data.size()>0 && stack_support.size()>0)27 {28 stack_data.pop_back();29 stack_support.pop_back();30 }31 32 }33 34 T min()35 {36 if (stack_data.size()>0 && stack_support.size()>0)37 {38 return stack_support.top();39 }40 41 42 }
问题2：实现在O(1)时间复杂度内，找出队列中的最小值。
思路：前文中我们实现了栈中O(1)找最小值，因此我们只需要通过两个栈（FILO）实现一个队列(FIFO)，就可以实现队列O(1)找到最小值。
即stack1的栈顶作为queue的入口，stack2的栈顶作为queue的出口。
C++代码：两个栈实现一个队列如下所示：
1 template <typename T> class NewQueue 2 { 3 private : 4 std::stack<T> stack1; 5 std::stack<T> stack2; 6 7 public: 8 9 NewQueue(void);10 ~NewQueue(void);11 12 13 void append(T value)14 {15 stack1.push_back(value);16 17 }18 19 T pop()20 { 21 //如果stack2为空，则从stack1拿元素中入栈到stack中22 if (stack2.size()<=0)23 {24 while(stack1.size()>0)25 { 26 T element = stack1.top(); 27 stack1.pop_back();28 stack2.push_back(element);29 30 }31 32 }33 // 如果已经没有元素可以出栈了34 if (stack2.size()==0)35 throw new exception("queue is empty.")36 37 T res = stack2.top();38 stack2.pop_back();39 return res;40 }41 42 }
如果要解决问题2, 只需结合代码1和2，在代码2中引入stack_support存放最小值即可：
代码如下：
1 template <typename T> class NewQueue 2 { 3 private : 4 std::stack<T> stack1; 5 std::stack<T> stack2; 6 std::stack<T> stack_support; 7 8 public: 9 10 NewQueue(void);11 ~NewQueue(void);12 13 14 void append(T value)15 {16 stack1.push_back(value);17 18 if (stack_support.size()==0 || stack_support.top()>value)19 stack_support.push_back(value);20 else:21 stack_support.push_back(stack_support.top());22 23 }24 25 T pop()26 { 27 //如果stack2为空，则从stack1拿元素中入栈到stack中28 if (stack2.size()<=0)29 {30 while(stack1.size()>0)31 { 32 T element = stack1.top(); 33 stack1.pop_back();34 stack2.push_back(element);35 36 }37 38 }39 // 如果已经没有元素可以出栈了40 if (stack2.size()==0 && stack_support.size()==0)41 throw new exception("queue is empty.")42 43 T res = stack2.top();44 stack2.pop_back();45 46 stack_support.pop_back();47 return res;48 49 T min()50 {51 if (stack2.size()>0 && stack_support.size()>0)52 {53 return stack_support.top();54 } 55 }56 57 58 }
用O(1)的时间复杂度，找到栈和队列中的最小（大）值
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。