155. Min Stack
题目名称
- Min Stack
题目描述
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
初试思路
获取最小值时，如果在获取时再遍历栈找到最小值是很慢的，所以在push和pop的时候保持最小值的动态更新。
初试代码
// 我的代码
class MinStack {
public:vector > a;MinStack() {}void push(int val) {if(isEmpty()){a.push_back({val, val});}else{a.push_back({val, min(val, a.back().second)}); }}void pop() {if(!isEmpty()){a.pop_back(); }}int top() {if(!isEmpty()){return a.back().first; }return 0;}int getMin() {if(!isEmpty()){return a.back().second; }return 0; }bool isEmpty(){ //这个函数也可以直接用vector的a.empty()代替cout<<(a.size()==0)<push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/
学到了啥
一、capacity相关函数
1.size:size_type size() const;
容器中元素个数。c.size();
2.max_size():size_type max_size() const;
返回最大容量。c.maxsize();
3.resize：void resize (size_type n, value_type val = value_type());
改变容器可以容纳元素的个数为n。如果n小于当前的容器大小，则保留前面n个元素，移除后面的。如果n大于当前容器大小，就扩展容器。value是初始值，如果n大于当前容器大小，则新增加的元素的值为value，若value省略，会自动调用一个默认值。
std::vector c;
for(int i=0;i<10;i++)
c.push_back(i);
c.resize(5);
c.resize(8,10);
c.resize(12);
for(int i=0;i 结果为：1 2 3 4 5 10 10 10 0 0 0 0 4.capacity:size_type capacity() const; 当前分配给容器的存储空间大小（元素个数），这并不限制容器的扩展，理论限制容器扩展大小是max_size的值 5.empty:bool empty() const; 返回容器是否为空while(!c.empty()){sum+=c.back(); 6.reserve:void reserve (size_type n); 使得capacity至少能容纳n个元素。 7.shrink_to_fit（C++11）:void shrink_to_fit(); 减小capacity，使其与容器大小相同 四、元素访问相关函数 1.[ ]操作:获取特定位置的元素。c[i]； 2.at:reference at (size_type n); 返回位置n处的元素。c.at(i),与c[i]差不多 3.front:reference front(); 返回容器中的第一个元素。c.front(); 4.back:reference back() 返回容器中最后一个元素。c.back(); 5.data（C++11）:value_type* data() noexcept; 返回一个指向容器中数组的指针c.data() int *p=c.data(); *p=10; ++p; *p=20; p[2]=100; 则c中存储的前面三个数据为10、20、100 五、更新操作 1.assign：template void assign (InputIterator first, InputIterator last); 给容器分配新的内容，并替换当前内容，同时修改大小,val为初始值 std::vectorfirst; std::vectorsecond; std::vectorthird; first.assign(7,100); std::vector::iterator it; it=first.begin()+1; second.assign(it,first.end()-1); int myints[]={1776,7,4}; third.assign(myints,myints+3); std::cout< 结果为：7 5 3 2.push_back: void push_back (const value_type& val); 在容器最后增加一个新的元素。c.push_back(n) 3.pop_back:void pop_back(); 移除最后一个元素。c.pop_back() 4.insert:iterator insert(iterator position,const value_type& val)：在position处插入元素val vector c(3,100); vector::iterator it; it=c.begin(); it=c.insert(it,200); c.insert(it,2,300); it=c.begin(); vector d(2,400); c.insert(it+2,d.begin(),d.end()); int s[]={501,502,503}; c.insert(c.begin(),s,s+3); 此时c中元素为：501 502 503 300 300 400 400 200 100 100 100 5.erase：iterator erase(iterator position):删除position处的元素std::cout<
c.pop_back();} const_reference at (size_type n) const;
const_reference front() const;
const_reference back() const;
const value_type* data() const noexcept;
void assign (size_type n, const value_type& val);void assign (initializer_list void insert(iterator position,size_type n,const value_type& val):在position处插入n个元素，插入的元素值初始化为valvoid insert(iterator position,InputIterator first,InputIterator last):在position处插入数组中从first到last的元素
iterator erase(iterator first,iterator last)：删除first到last的元素
上一篇：Activity 的启动模式