每日一题---day7

基础题：

实现一个栈Stack，要求Push(出栈)、Pop（入栈），Min(返回最小值的操作)的时间复杂度为O(1)

代码：

#include<stack>
template<class T>
class Stack
{
public:
 void Push(T x)
 {
 if(min.empty())
 {
 min.push(x);
 s.push(x);
 }
 else
 {
 if( x < min.top())
 {
 min.pop();
 min.push(x);
 }
 s.push(x);
 }
 }
 void Pop()
 {
 if(s.top() == min.top())
 {
 min.pop();
 }
 s.pop();
 }
 T Top()
 {
return s.top();
 }
 T Min()
 {
 if(!min.empty())
    return min.top();
 }
 bool Empty()
 {
 return s.empty();
 }
private:
stack<T> s;
stack<T> min;
};

附加题

查找一个字符串中第一个只出现两次的字符，比如：“abcdefabcdefabc”,中第一个只出现两次的字符为‘d’,要求时间复杂度为O(N),空间复杂度O(1)