目录
1.最小栈
*2.栈的压入、弹出序列
3.逆波兰表达式
3.队列实现栈
4.二叉树的层序遍历（运用队列）
5.找出数组中第k大的元素
1.最小栈
力扣
删除最小值1后要遍历一遍剩下的数才能找到剩下数里面的最小值 。极端情况下如果数组为降序
应该随时记录对应位置的最小值，考虑用双栈（以空间换时间）
还可以继续优化：minst中没必要push相同的值
还是存在重复的情况
class MinStack {
public:
MinStack() {
}
void push(int val) {
_st.push(val);
if(_minst.empty()||val <= _minst.top())
{
_minst.push(val);
}
}
void pop() {
if(_st.top() == _minst.top())
{
_minst.pop();
}
_st.pop();
}
int top() {
return _st.top();
}
int getMin() {
return _minst.top();
}
private:
stack_st;
stack_minst;
};
极端场景：假设插入的重复数据很多，能否对minst再优化，让minst中少存储一些重复数据？
struct val_Count
{
int _val;
int _count;
};
class MinStack {
public:
MinStack() {
}
void push(int val) {
_st.push(val);
if(_minst.empty()||val <= _minst.top())
{
_minst.push(val);
}
}
void pop() {
if(_st.top() == _minst.top())
{
_minst.pop();
}
_st.pop();
}
int top() {
return _st.top();
}
int getMin() {
return _minst.top();
}
private:
stack_st;
stack_minst;
};
class MinStack
{
public:
void push(int x)
{
// 只要是压栈，先将元素保存到_elem中
_elem.push(x);
// 如果x小于_min中栈顶的元素，将x再压入_min中
if (_min.empty() || x <= _min.top())
_min.push(x);
}
void pop()
{
// 如果_min栈顶的元素等于出栈的元素，_min顶的元素要移除
if (_min.top() == _elem.top())
_min.pop();
_elem.pop();
}
int top() { return _elem.top(); }
int getMin() { return _min.top(); }
private:
// 保存栈中的元素
std::stack _elem;
// 保存栈的最小值
std::stack _min;
};
*2.栈的压入、弹出序列
使用栈的入栈和出栈来模拟这个出栈顺序，如果能模拟出来，就说明是合法的，如果不能模拟，就不是合法的
1.先把push数组中的值入栈
2.pop数组的值跟栈里面的数据比较，如果相等，则pop数组往后走，不断出栈里面的数据，直到不相等或者栈为空，重复第一步即可
结束条件：push数组走完就结束
判断是否匹配：如果pop数组走完了，就是匹配的；如果pop数组没走完，就是不匹配的
class Solution {
public:
bool IsPopOrder(vector pushV,vector popV) {
stackst;
int i = 0;
int j = 0;
while(i
class Solution {
public:
bool IsPopOrder(vector pushV, vector popV) {
//入栈和出栈的元素个数必须相同
if (pushV.size() != popV.size())
return false;
// 用s来模拟入栈与出栈的过程
int outIdx = 0;
int inIdx = 0;
stack s;
while (outIdx < popV.size())
{
// 如果s是空，或者栈顶元素与出栈的元素不相等，就入栈
while (s.empty() || s.top() != popV[outIdx])
{
if (inIdx < pushV.size())
s.push(pushV[inIdx++]);
else
return false;
}
// 栈顶元素与出栈的元素相等，出栈
s.pop();
outIdx++;
}
return true;
}
};
3.逆波兰表达式
中缀表达式如何转换成后缀表达式？
class Solution {
public:
void getOPNum(stack& st,int& left,int& right)
{
right = st.top();
st.pop();
left = st.top();
st.pop();
}
int evalRPN(vector& tokens) {
stack st;
for(const auto& str:tokens)
{
int left,right;
switch(str[0])//或者用str.back()
{
case '+':
getOPNum(st,left,right);
st.push(left + right);
break;
case '-':
if(str.size() == 1)
{
getOPNum(st,left,right);
st.push(left - right);
break;
}
else
{
st.push(stoi(str));
}
break;
case '*':
getOPNum(st,left,right);
st.push(left * right);
break;
case '/':
getOPNum(st,left,right);
st.push(left / right);
break;
default:
st.push(stoi(str));
break;
}
}
return st.top();
}
};
class Solution {
public:
int evalRPN(vector& tokens) {
stack s;
for (size_t i = 0; i < tokens.size(); ++i)
{
string& str = tokens[i];
// str为数字
if (!("+" == str || "-" == str || "*" == str || "/" == str))
{
s.push(atoi(str.c_str()));
}
else
{
// str为操作符
int right = s.top();
s.pop();
int left = s.top();
s.pop();
switch (str[0])
{
case '+':
s.push(left + right);
break;
case '-':
s.push(left - right);
break;
case '*':
s.push(left * right);
break;
case '/':
// 题目说明了不存在除数为0的情况
s.push(left / right);
break;
}
}
}
return s.top();
}
};
3.队列实现栈
力扣
class MyStack {
public:
MyStack() {
}
void push(int x) {
if(!_q1.empty())
{
_q1.push(x);
}
else
{
_q2.push(x);
}
}
int pop() {
queue*emptyQ = &_q1;
queue*nonemptyQ = &_q2;
if(!_q1.empty())
{
swap(emptyQ,nonemptyQ);
}
while(nonemptyQ->size()>1)
{
emptyQ->push(nonemptyQ->front());
nonemptyQ->pop();
}
int top = nonemptyQ->front();
nonemptyQ->pop();
return top;
}
int top() {//取栈顶数据
if(!_q1.empty())
{
return _q1.back();
}
else
{
return _q2.back();
}
}
bool empty() {
return _q1.empty()&&_q2.empty();
}
queue_q1;
queue_q2;
};
4.二叉树的层序遍历（运用队列）
力扣
class Solution {
public:
vector> levelOrder(TreeNode* root) {
queueq;
int levelSize;
if(root)
{
q.push(root);
levelSize = 1;
}
vector>vv;
while(!q.empty())
{
//控制着，一层一层出
vectorv;
for(int i = 0;ival);
//一个节点出来要把其下一层数据代入
if(front->left)
{
q.push(front->left);
}
if(front->right)
{
q.push(front->right);
}
}
//上一层出完了，下一层就都入队列了，队列size就是下一层的数据个数
levelSize = q.size();
vv.push_back(v);
}
return vv;
}
};
return之前加上reverse(vv.begin(),vv.end()); 即可实现从下往上层序遍历
5.找出数组中第k大的元素
力扣
法一
class Solution {
public:
int findKthLargest(vector& nums, int k) {
sort(nums.begin(),nums.end());
return nums[nums.size()-k];
}
};
法二：
class Solution {
public:
int findKthLargest(vector& nums, int k) {
// 将数组中的元素先放入优先级队列中
priority_queue p(nums.begin(), nums.end());
// 将优先级队列中前k-1个元素删除掉
for (int i = 0; i < k - 1; ++i)
{
p.pop();
}
return p.top();
}
};
时间复杂度：O(N+k*logN)
空间复杂度：O(N)
法三：传反向迭代器即为降序
class Solution {
public:
int findKthLargest(vector& nums, int k) {
sort(nums.rbegin(),nums.rend());
return nums[k-1];
}
};
法四
class Solution {
public:
int findKthLargest(vector& nums, int k) {
sort(nums.begin(),nums.end(),greater());//greater后面要加括号，类型后面加上括号就是对象
return nums[k-1];
}
};
法五
class Solution {
public:
int findKthLargest(vector& nums, int k) {
//k个小堆
priority_queue,greater>kMinHeap(nums.begin(),nums.begin()+k);
for(size_t i = k;i kMinHeap.top())
{
kMinHeap.pop();
kMinHeap.push(nums[i]);
}
}
return kMinHeap.top();
}
};
时间复杂度：O(K+(N-K)*logK)
空间复杂度: O(K)
