C++STL之stack和queue容器适配器: 相关习题解析
1. 最小栈
思路:
一、整体架构
- 使用两个栈
st和min_st分别实现不同的功能。
st用于存放插入的数据，即主要的数据存储栈，模拟常规的数据存储结构。min_st用于存放最小的元素，通过特定的插入和弹出规则，始终保持栈顶为当前st中的最小元素。二、插入操作（push）
- 对于
st：
- 正常插入新元素，无论该元素的大小如何，都直接将其压入
st。这保证了数据的完整存储，不进行任何筛选或特殊处理。- 对于
min_st：
- 当
min_st第一次为空时，先插入一个元素。这是初始化操作，确保min_st有一个起始元素，以便后续进行比较和更新。- 如果插入的元素比
min_st的栈顶元素小，就将该元素插入min_st。这样做的目的是当有新的更小元素出现时，更新min_st的栈顶，使其始终保持当前st中的最小元素在栈顶。例如，如果当前min_st的栈顶是 5，新插入的元素是 4，那么将 4 压入min_st，此时min_st的栈顶变为 4，代表当前最小元素为 4。三、弹出操作（pop）
- 对于
st：
- 正常弹出栈顶元素。按照栈的先进后出原则，删除最后插入
st的元素。- 对于
min_st：
- 在弹出
st的元素后，需要检查该元素是否与min_st的栈顶元素相等。如果相等，说明当前要弹出的元素是最小元素，那么也需要将min_st的栈顶元素弹出。这是为了保持两个栈的同步，确保min_st始终反映st中的最小元素。例如，如果st和min_st的栈顶都是 4，当从st中弹出 4 时，也需要从min_st中弹出 4，以保证min_st的栈顶仍然是st中剩余元素的最小元素。
class MinStack {
public:
stack<int> st;
stack<int> min_st;
MinStack()
{
}
void push(int val)
{
st.push(val);
if(min_st.empty() || val <= min_st.top())
{
min_st.push(val);
}
}
void pop()
{
if(st.top() == min_st.top())
{
min_st.pop();
}
st.pop();
}
int top()
{
return st.top();
}
int getMin()
{
return min_st.top();
}
};
2. 栈的弹出压入序列
思路：
首先遍历压入顺序的序列。在遍历过程中，将压入顺序中的元素依次压入辅助栈，同时不断检查辅助栈的栈顶元素是否与弹出顺序的当前元素相等。如果相等，就将辅助栈的栈顶元素弹出，并移动弹出顺序的索引。继续这个过程，直到压入顺序的所有元素都被处理完。最终，如果辅助栈为空，说明给定的压入顺序和弹出顺序是合法的栈的操作顺序；如果辅助栈不为空，则说明不是合法的弹出顺序。
class Solution {
public:
bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
int pushi = 0;
int popi = 0;
stack<int> st;
while (pushi < pushV.size())
{
st.push(pushV[pushi]);
++pushi;
while (!st.empty() && st.top() == popV[popi])
{
st.pop();
++popi;
}
}
return st.empty();
}
};3. 逆波兰表达式求值
4. 用栈实现队列
5. 用队列实现栈
6. 数组中第K个大的元素
方法一：优先级队列求解
把数组的数据入队，然后pop前 k-1 个数据，栈顶就是第 K 大的数。
时间复杂度：堆排序的时间复杂度是 N*logN,取最坏，时间复杂度是 N*logN。
空间复杂：构建了堆，空间复杂度是O(N)。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k)
{
priority_queue<int> pq;
for(auto& e : nums)
{
pq.push(e);
}
while(--k)
{
pq.pop();
}
return pq.top();
}
};
方法二：排序
排序的底层是快排，快排使用三数取中法，避免了最坏的情况。
时间复杂度是 O(N*logN)
空间复杂度是 O(1)
class Solution {
public:
int findKthLargest(vector<int>& nums, int k)
{
sort(nums.begin(), nums.end());
return nums[nums.size() - k];
}
};
7. 有效的括号
8. 字符串解码
9. 每日温度
10. 柱状图中最大的矩形
原文地址：https://blog.csdn.net/m0_63207201/article/details/142341302
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！