- 栈和队列也是SGI STL里面的数据结构，栈后进先出，队列先进先出，栈和队列都不提供迭代器
- SGI STL中 栈和队列的底层实现缺省的情况下都是用 deque 双端队列实现的
- 利用栈和队列的性质解题
- 单调栈
- 单调队列
- 优先队列
- 链接https://leetcode.cn/problems/implement-queue-using-stacks/
- 解题方法：利用栈和队列的性质
- leetcode解题代码
class MyQueue {
public:
stack<int> a, b;
MyQueue() {
}
void push(int x) {
a.push(x);
}
int pop() {
// 保留一个元素用来返回答案
while (a.size() > 1) b.push(a.top()), a.pop();
int cur = a.top();
a.pop();
// 恢复现场
while (b.size()) a.push(b.top()), b.pop();
return cur;
}
int peek() {
while (a.size() > 1) b.push(a.top()), a.pop();
int cur = a.top();
while (b.size()) a.push(b.top()), b.pop();
return cur;
}
bool empty() {
return a.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
- 链接https://leetcode.cn/problems/implement-stack-using-queues/
- 解题方法：
在获取队头元素的时候和上一题有所区别 - leetcode解题代码
class MyStack {
public:
queue<int> a, b;
MyStack() {
}
void push(int x) {
a.push(x);
}
int pop() {
while (a.size() > 1) b.push(a.front()), a.pop();
auto cur = a.front();
a.pop();
while (b.size()) a.push(b.front()), b.pop();
return cur;
}
int top() {
while (a.size() > 1) b.push(a.front()), a.pop();
auto cur = a.front();
b.push(a.front()), a.pop();
while (b.size()) a.push(b.front()), b.pop();
return cur;
}
bool empty() {
return a.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
- 链接https://leetcode.cn/problems/valid-parentheses/
- 解题方法1：先将所有的左括号入栈，注意入栈顺序要跟匹配顺序相同
如果右括号与当前栈顶左括号匹配，那么弹出栈顶元素，否则返回 false，直到栈为空匹配完成 - leetcode解题代码
class Solution {
public:
bool isValid(string s) {
stack<char> stk;
for (auto c: s){
if (c == '(' || c == '[' || c == '{') stk.push(c);
else if (c == ')'){
if (stk.empty() || stk.top() != '(')
return false;
stk.pop();
}
else if (c == ']'){
if (stk.empty() || stk.top() != '[')
return false;
stk.pop();
}
else if (c == '}'){
if (stk.empty() || stk.top() != '{')
return false;
stk.pop();
}
}
return stk.empty();
}
};
- 解题方法2：先将所有的左括号入栈，注意入栈顺序要跟匹配顺序相同
匹配右括号，可以查询 ASKII 码发现无论是大中小括号，其左右括号的 ASKII 码相差小于等于 2 - leetcode解题代码
class Solution {
public:
bool isValid(string s) {
stack<char> stk;
for (auto c: s){
if (c == '(' || c == '[' || c == '{') stk.push(c);
else {
if (stk.empty() || abs(c - stk.top()) > 2) return false;
stk.pop();
}
}
return stk.empty();
}
};
- 链接https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
- 解题方法：遍历所有字符，如果栈不空且栈顶元素与遍历的当前元素相同，删除栈顶元素，否则将当前元素加入栈中
遍历栈加入答案数组，由于栈是先入后出所以最后需要反转答案数组 - leetcode解题代码
class Solution {
public:
string removeDuplicates(string s) {
stack<char> stk;
string res;
for (auto c: s){
if (stk.size() && stk.top() == c) stk.pop();
else stk.push(c);
}
while (stk.size()){
res += stk.top();
stk.pop();
}
reverse(res.begin(), res.end());
return res;
}
};
- 链接https://leetcode.cn/problems/evaluate-reverse-polish-notation/
- 解题方法：遍历所有字符，如果字符为运算符则将当前栈顶的两个元素弹出做相应计算（注意：弹出是先弹出后面的元素，减法和除法需要注意元素计算顺序）
如果字符为数字，则入栈（注意转换格式），最后返回栈顶元素的值即为答案 - leetcode解题代码
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> stk;
for (auto c: tokens){
if (c == "+" || c == "-" || c == "*" || c == "/"){
long b = stk.top(); stk.pop();
long a = stk.top(); stk.pop();
if (c == "+") stk.push(a + b);
else if (c == "-") stk.push(a - b);
else if (c == "*") stk.push(a * b);
else if (c == "/") stk.push(a / b);
}
else stk.push(stoi(c));
}
return stk.top();
}
};
- 常见模型：找出每个数左边/右边离它最近的比它大/小的数
- 如果是找左边第一个比它小/大的数，那么从左往右遍历入栈，如果当前数小于等于/大于等于栈顶元素，那么栈顶元素永远不可能作为答案输出，则删除栈顶元素
- 如果是找右边第一个比它小/大的数，那么从右往左遍历入栈，如果当前数小于等于/大于等于栈顶元素，那么栈顶元素永远不可能作为答案输出，则删除栈顶元素
- 单调栈模板
for (int i = 0; i < n; i ++){
while (stk.size() && check(nums[i])) stk.pop();
...
stk.push();
}
for (int i = n - 1; i >= 0; i --){
while (stk.size() && check(nums[i])) stk.pop();
...
stk.push();
}
给定一个长度为
输入格式
第一行包含整数
第二行包含
输出格式
共一行，包含
数据范围
输入样例：
5
3 4 2 7 5
输出样例：
-1 3 -1 2 2
- 解题代码
#include <iostream>
#include <stack>
using namespace std;
const int N = 1e5 + 10;
int n;
int nums[N];
int main(){
cin >> n;
for (int i = 0; i < n; i ++) cin >> nums[i];
stack<int> stk;
for (int i = 0; i < n; i ++){
while (stk.size() && nums[i] <= stk.top()) stk.pop();
if (stk.size()) cout << stk.top() << ' ';
else cout << -1 << ' ';
stk.push(nums[i]);
}
return 0;
}
- 链接https://leetcode.cn/problems/daily-temperatures/
- 解题方法：单调栈模板
- leetcode解题代码
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& t) {
stack<int> stk;
vector<int> res(t.size());
for (int i = t.size() - 1; i >= 0; i --){
while (stk.size() && t[i] >= t[stk.top()]) stk.pop();
if (stk.size()) res[i] = stk.top() - i;
stk.push(i);
}
return res;
}
};
- 链接https://leetcode.cn/problems/next-greater-element-i/
- 解题方法：单调栈模板
- leetcode解题代码
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int> stk;
vector<int> q(nums2.size());
// 找到 nums2 中每个数的下一个更大元素，存在数组 q 中
for (int i = nums2.size() - 1; i >= 0; i --){
while (stk.size() && nums2[i] >= stk.top()) stk.pop();
if (stk.size()) q[i] = stk.top();
else q[i] = -1;
stk.push(nums2[i]);
}
// 用哈希表存 nums2 中每个元素的下标
unordered_map<int, int> hash;
for (int i = 0; i < nums2.size(); i ++) hash[nums2[i]] = i;
vector<int> res;
// 找到 nums1 中元素在 nums2 中对应的下标，将数组 q 中的值取出来即为答案
for (auto c: nums1){
res.push_back(q[hash[c]]);
}
return res;
}
};
- 链接https://leetcode.cn/problems/next-greater-element-ii/
- 解题方法：解决环形问题，可以将数组复制一份接到原数组之后
同样用单调栈模板解题 - leetcode解题代码
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
stack<int> stk;
vector<int> res(n * 2);
nums.insert(nums.end(), nums.begin(), nums.end());
for (int i = n * 2 - 1; i >= 0; i --){
while (stk.size() && nums[i] >= stk.top()) stk.pop();
if (stk.size()) res[i] = stk.top();
else res[i] = -1;
stk.push(nums[i]);
}
res.resize(n);
return res;
}
};
- 常见模型：找出滑动窗口中的最大/最小值
- 如果求滑动窗口的最大值那么即为一个递减序列（队头为最大值），如果当前元素大于等于队尾元素，那么队尾元素永远不可能作为结果输出，删除队尾元素
- 如果求滑动窗口的最小值那么即为一个递增序列（队头为最小值），如果当前元素小于等于队尾元素，那么队尾元素永远不可能作为结果输出，删除队尾元素
- 单调队列模板
for (int i = 0; i < n; i ++ )
{
// 合法性判断（是否超出滑动窗口的大小）
if (q.size() && check()) q.pop_front(); // 判断队头是否滑出窗口
// 单调性判断（添加的元素是否符合队列单调性）
while (q.size() && check()) q.pop_back();
// 在队尾添加元素
q.push_back(i);
// 能够形成滑动窗口了开始维护答案
if (i >= k - 1) res.push_back();
}
给定一个大小为
有一个大小为
你只能在窗口中看到
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，$k$ 为
| 窗口位置 | 最小值 | 最大值 |
|---|---|---|
| [1 3 -1] -3 5 3 6 7 | -1 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 3 | 7 |
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数
第二行有
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
输入样例：
8 3
1 3 -1 -3 5 3 6 7
输出样例：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
- 解题代码
#include <iostream>
#include <deque>
using namespace std;
const int N = 1e6 + 10;
int n, k;
int nums[N];
int main(){
cin >> n >> k;
for (int i = 0; i < n; i ++) cin >> nums[i];
deque<int> q1;
for (int i = 0; i < n; i ++){
if (q1.size() && i - q1.front() + 1 > k) q1.pop_front();
while (q1.size() && nums[i] <= nums[q1.back()]) q1.pop_back();
q1.push_back(i);
if (i >= k - 1) cout << nums[q1.front()] << ' ';
}
puts("");
deque<int> q2;
for (int i = 0; i < n; i ++){
if (q2.size() && i - q2.front() + 1 > k) q2.pop_front();
while (q2.size() && nums[i] >= nums[q2.back()]) q2.pop_back();
q2.push_back(i);
if (i >= k - 1) cout << nums[q2.front()] << ' ';
}
}
- 链接https://leetcode.cn/problems/sliding-window-maximum/
- 解题方法：单调队列模板
- leetcode解题代码
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> q;
vector<int> res;
for (int i = 0; i < nums.size(); i ++){
while (q.size() && i - q.front() + 1 > k) q.pop_front();
while (q.size() && nums[i] >= nums[q.back()]) q.pop_back();
q.push_back(i);
if (i >= k - 1) res.push_back(nums[q.front()]);
}
return res;
}
};
- 优先队列是一种会按照默认或自定义的优先级进行自动排序的队列，其特点是优先级高的元素排在队首，低的排在队尾，可以理解为维护一个堆
- 头文件
#include <queue>中提供了两种可直接引用的优先规则（排序规则）：greater、less；其中，less 是默认优先规则，小的元素排在堆底，大的元素在堆顶也叫大根堆；greater 表示小根堆，大的元素排在堆底，小的元素在堆顶
- 链接https://leetcode.cn/problems/kth-largest-element-in-an-array/
- 解题方法：优先队列
- leetcode解题代码
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// 优先队列，建小根堆即堆顶元素为最小值，这样更新的时候可以删除堆顶元素
priority_queue<int, vector<int>, greater<int>> heap;
// 直接入堆，如果大于 k 则删除元素（删除的都是最小值）
for (auto c: nums){
heap.push(c);
if (heap.size() > k){
heap.pop();
}
}
// 输出
return heap.top();
}
};
- 链接https://leetcode.cn/problems/top-k-frequent-elements/
- 解题方法：优先队列
- leetcode解题代码
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
// 用哈希表记录每个数字出现的次数
unordered_map<int, int> hash;
for (auto c: nums) hash[c] ++;
// 重载优先队列排序，pair<数字，出现的次数>，以数字出现的次数排序
struct mycompare{
bool operator () (const pair<int, int> &a, const pair<int, int> &b){
return a.second > b.second;
}
};
// 定义优先队列
priority_queue<pair<int, int>, vector<pair<int, int>>, mycompare> heap;
// 将哈希表入队，如果元素个数超过 k 则删除堆顶元素（最小值）
for (auto x: hash){
heap.push(x);
if (heap.size() > k){
heap.pop();
}
}
// 输出结果，输出的是 pair 中的数字
vector<int> res;
while (heap.size()){
res.push_back(heap.top().first);
heap.pop();
}
return res;
}
};
- 链接https://leetcode.cn/problems/merge-k-sorted-lists/
- 解题方法：优先队列
- leetcode解题代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
// 重载比较函数，将小的元素放在堆顶，大的元素放在堆底
struct Cmp{
bool operator() (ListNode* a, ListNode* b){
return a->val > b->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
auto dummy = new ListNode(-1);
auto cur = dummy;
// 将所有链表数组入堆，会自动排序将头元素进行排序
for (auto c: lists)
if (c) heap.push(c);
while (heap.size()){
auto t = heap.top();
heap.pop();
cur = cur->next = t;
if (t->next) heap.push(t->next);
}
return dummy->next;
}
};