剑指 Offer 30. 包含min函数的栈(LeetCode 115.最小栈)
题目链接:
解法1:自定义栈类,链表实现——只需在普通栈(的每个节点)中保存一个minv记录最小值,每次push时更新即可
解法1代码:
class MinStack {
struct Node
{
int val;
int minv;
Node* nextn;
Node(int t_val, int t_minv):
val(t_val),
minv(t_minv),
nextn(nullptr)
{ }
};
private:
Node* head; // head 来表示栈顶
public:
MinStack() {
head = nullptr;
}
~MinStack() {
while (head != nullptr)
{
Node* it = head;
head = head->nextn;
delete it;
it = nullptr;
}
}
void push(int t_val) {
if(head == nullptr) {
head = new Node{t_val, t_val};
} else {
int tmp_min = t_val < head->minv ? t_val : head->minv;
Node* cur = new Node(t_val, tmp_min);
cur->nextn = head;
head = cur;
}
}
void pop() {
// 每个节点都有自己记录的minv,最小值的点被pop后,nextn保存了第二小的值
Node* it = head;
head = head->nextn;
delete it;
it = nullptr;
}
int top() {
return head->val;
}
int getMin() {
return head->minv;
}
};
解法2:使用两个stack<int>辅助栈——不需要自定义栈
解法2代码:
class MinStack {
private:
stack<int> dataStack;
stack<int> minStack;
public:
MinStack() {
}
void push(int t_val) {
dataStack.push(t_val);
if(minStack.empty()) {
minStack.push(t_val);
} else {
minStack.push(t_val<minStack.top()?t_val:minStack.top());
}
}
void pop() {
dataStack.pop();
minStack.pop();
}
int top() {
return dataStack.top();
}
int min() {
return minStack.top();
}
};
解法3:使用一个stack<Node>栈——自定义Node(int val, int minv),无需定义指针
解法3代码:
#include <iostream>
#include <stack>
using namespace std;
class MinStack {
struct Node
{
int val;
int minv;
Node(int t_val, int t_minv):
val(t_val),
minv(t_minv)
{ }
};
private:
stack<Node> stk;
public:
MinStack() {
}
void push(int t_val) {
if(stk.empty()) {
stk.push(Node{t_val, t_val});
} else {
int tmp_min = t_val < stk.top().minv ? t_val : stk.top().minv;
stk.push(Node{t_val, tmp_min});
}
}
void pop() {
stk.pop();
}
int top() {
return stk.top().val;
}
int min() {
return stk.top().minv;
}
};
int main()
{
MinStack* obj = new MinStack();
obj->push(-2);
obj->push(0);
obj->push(-3);
cout << obj->min() << endl;
obj->pop();
cout << obj->top() << endl;
cout << obj->min() << endl;
return 0;
}
下面主要整理了vector的不同按值删除方法,但是解法不符合题目要求。
参考:
- https://blog.csdn.net/haimianjie2012/article/details/118812615
- http://c.biancheng.net/view/6846.html
- https://www.runoob.com/note/27430
- https://www.coonote.com/cplusplus-note/vector-item-delete.html
代码:
#if 0
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
class MinStack {
public:
stack<int> stk;
vector<int> vec;
MinStack() {
}
void push(int x) {
stk.push(x);
vec.push_back(x);
}
void pop() {
for(auto it=vec.begin(); it!=vec.end(); )
{
if(*it == stk.top())
{
it = vec.erase(it);
break;
}
else
{
it++;
}
}
stk.pop();
}
int top() {
return stk.top();
}
int min() {
sort(vec.begin(), vec.end());
return vec.front();
}
};
int main()
{
// MinStack* obj = new MinStack();
// obj->push(-2);
// obj->push(0);
// obj->push(-3);
// cout << obj->min() << endl;
// obj->pop();
// cout << obj->top() << endl;
// cout << obj->min() << endl;
int a[7] = {1, 2, 3, 3, 4, 5, 3};
// 通过数组a的地址初始化,注意地址是从0到5(左闭右开区间)
vector<int> b(a, a + 7);
vector<int>::iterator it;
cout << b.size() << " " <<b.capacity() <<endl;
b.push_back(2);
cout << b.size() << " " <<b.capacity() <<endl;
// b.size() or b.capacity() 容量不足时每次扩充一倍
for(it = b.begin(); it != b.end(); )
{
if(*it == 3)
it = b.erase(it);
else
it++;
}
// 或者
// for(int i = 0; i < b.size(); )
// {
// if(b[i] == 3)
// b.erase(b.begin()+i);
// else
// i++;
// }
// 或者使用algorithm头文件中的remove函数
// auto iter = std::remove(b.begin(), b.end(), 3);
// b.erase(iter, b.end());
// 或者使用algorithm头文件中的find函数
// auto it = find(b.begin(), b.end(), 3);
// if(it != b.end())
// {
// b.erase(it);
// }
for(it = b.begin(); it != b.end(); it++)
{
cout << *it << "\t" ;
}
cout << "\n" << endl ;
// vector<int> ggv;
// for(int i=1;i<=33;i++)
// {
// ggv.push_back(i);
// cout << ggv.size() << " " <<ggv.capacity() <<endl;
// }
return 0;
}
#endif
#if 01
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
vector<int> demo{1,3,3,4,3,5};
// 头文件algorithm中的remove函数,删除demo中值为3的元素
// 该函数没有改变demo的size,只是把删除后的结果存储在前iter个位置
auto iter = std::remove(demo.begin(), demo.end(), 3);
// demo.erase(iter, demo.end());
// 交换要删除元素和最后一个元素的位置,等同于 swap(demo[1],demo[4])
// swap( *(std::begin(demo)+1), *(std::end(demo)-1) );
// 删除 2、3
// auto iter = demo.erase(demo.begin()+1, demo.end()-2);
cout << "size is: " << demo.size() << endl;
cout << "capacity is: " << demo.capacity() << endl;
// 输出剩余的元素
for (auto first = demo.begin(); first < iter;++first) {
cout << *first << "\t";
}
cout << "\n" << endl;
// 无法使用之前的方法遍历容器,而是需要像上面,借助remove()返回的迭代器完成正确的遍历
for(auto it = demo.begin(); it != demo.end(); it++)
{
cout << *it << "\t" ;
}
cout << "\n" << endl;
return 0;
}
#endif