1. 最小栈
. - 力扣（LeetCode）
思路:
一、整体架构
- 使用两个栈
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. 逆波兰表达式求值
. - 力扣（LeetCode）
4. 用栈实现队列
. - 力扣（LeetCode）
5. 用队列实现栈
. - 力扣（LeetCode）
6. 数组中第K个大的元素
. - 力扣（LeetCode）
方法一：优先级队列求解
把数组的数据入队，然后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. 有效的括号
. - 力扣（LeetCode）
8. 字符串解码
. - 力扣（LeetCode）
9. 每日温度
. - 力扣（LeetCode）
10. 柱状图中最大的矩形
. - 力扣（LeetCode）
