- 用两个栈实现队列的头部出队，尾部入队操作：
class Solution
{
public:
void push(int node) {
while(!stack2.empty())
{
stack1.push(stack2.top());
stack2.pop();
}
stack1.push(node);
}
int pop() {
while(!stack1.empty())
{
stack2.push(stack1.top());
stack1.pop();
}
int ans = stack2.top();
stack2.pop();
return ans;
}
private:
stack<int> stack1;
stack<int> stack2;
};
30、包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为
）。
- 解题思路：复杂度是
class Solution {
public:
void push(int value) {
st1.push(value);
if(st2.empty())
st2.push(value);
else
{
int top = st2.top();
if(top>value)
st2.push(value);
else
st2.push(top);
}
}
void pop() {
st1.pop();
st2.pop();
}
int top() {
return st1.top();
}
int min() {
return st2.top();
}
private:
stack<int> st1;
stack<int> st2;
};
31、栈的压入和弹出
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
- 解：比较进栈数组中对每一个进栈的数与出栈数组的第一个元素，相等则对该元素出栈，继续比较进栈数组出栈后的栈顶与出栈数组第二个元素，相等则弹出，否则，继续进栈。若是最后进栈数组为空，则结果匹配正确。
class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
if(pushV.empty() && popV.empty()) return true;
if(pushV.empty() || popV.empty() || pushV.size()!=popV.size()) return false;
stack<int> st;
for(int i=0,j=0; i<pushV.size();++i)
{
st.push(pushV[i]);
//未越界且相等
while(j<popV.size() && popV[j]==st.top())
{
st.pop();
j++;
}
}
if(st.empty())
return true;
else
return false;
}
};
59、队列最大的值
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}
1.直接算最大再排除第一个：这个算法总的时间复杂度是O(nk)
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
vector<int> ans;
deque<int> index;
if(num.empty() || size == 1) return num;
if(size<=0) return vector<int>();
int count = 0; //记录滑动窗口大小是否达到
for(int i=0; i<num.size();++i)
{
index.push_back(num[i]);
count++;
if(count==size)
{
count -= 1;
ans.push_back(*max_element(index.begin(), index.end()));
index.pop_front();
}
}
return ans;
}
};
用双向队列实现，主要是理解思路。
从后删除的情况：只有当 当前数字比队列的后面数字大时。
从前删除的情况： 只有 当 队列前面的数字的序号不在滑动窗口内。
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
vector<int> res;
deque<int> s;
for(unsigned int i=0;i<num.size();++i){
while(s.size() && num[s.back()]<=num[i])//从后面依次弹出队列中比当前num值小的元素，同时也能保证队列首元素为当前窗口最大值下标,同时排出多个
s.pop_back();
//这里的while改为if也是可行的，因为只可能超出一个
while(s.size() && i-s.front()+1>size)//当当前窗口移出队首元素所在的位置，即队首元素坐标对应的num不在窗口中，需要弹出
s.pop_front();
s.push_back(i);//把每次滑动的num下标加入队列
if(size&&i+1>=size)//当滑动窗口首地址i大于等于size时才开始写入窗口最大值
res.push_back(num[s.front()]);
}
return res;
}
};
网友评论