目录
一、栈与队列基础知识
232.用栈实现队列
225. 用队列实现栈
1047. 删除字符串中的所有相邻重复项
二、栈的应用
20. 有效的括号
150. 逆波兰表达式求值
71. 简化路径
三、队列的应用
239. 滑动窗口最大值
四、优先队列
347.前 K 个高频元素
一、栈与队列基础知识 232.用栈实现队列
class MyQueue {
public:
MyQueue() {
}
void push(int x) {
this->sIn.push(x);
}
int pop() {
//sOut为先入元素，为空时将sIn内元素全部导入
if (this->sOut.empty()) {
while (!this->sIn.empty()) {
this->sOut.push(this->sIn.top());
this->sIn.pop();
}
}
int res = this->sOut.top();
this->sOut.pop();
return res;
}
int peek() {
int res = this->pop();
this->push(res);
return res;
}
bool empty() {
return this->sIn.empty() && this->sOut.empty();
}
private:
stack sIn;
stack sOut;
};
利用两个栈实现，一个入队用，一个出队用。
注意两点：1.enpty()函数的简化写法；2.peek()函数复用了pop()函数，能使用代码复用的地方，尽量不要复制粘贴代码。
225. 用队列实现栈class MyStack {
public:
MyStack() {
}
void push(int x) {
this->qMain.push(x);
}
int pop() {
int size = this->qMain.size() - 1;
//把队列1中的元素导入队列2，但保留最后一个元素
while (size--) {
this->qBackup.push(this->qMain.front());
this->qMain.pop();
}
int res = this->qMain.front();
this->qMain.pop();
//把队列2拷贝给队列1，然后清空队列2
this->qMain = this->qBackup;
while (!this->qBackup.empty()) {
this->qBackup.pop();
}
return res;
}
int top() {
int res = this->pop();
this->push(res);
return res;
}
bool empty() {
return this->qMain.empty();
}
private:
queue qMain;
queue qBackup;
}; 用第二个队列作为第一个队列的备份，每次pop()时除最后一个元素外全部入队第二个队列。
1047. 删除字符串中的所有相邻重复项string removeDuplicates(string s) {
stack filter;
for (int i = s.size() - 1; i >= 0; i--) {
if (filter.empty()) filter.push(s[i]);
else if (s[i] == filter.top()) filter.pop();
else filter.push(s[i]);
}
string res;
while (!filter.empty()) {
res += filter.top();
filter.pop();
}
return res;
} 本题也可以将字符串作为栈，利用push_back和pop_back直接实现。
二、栈的应用 20. 有效的括号
bool isValid(string s) {
stack rightRecord;
for (auto i : s) {
if (i == '(') rightRecord.push(')');
else if (i == '{') rightRecord.push('}');
else if (i == '[') rightRecord.push(']');
//若需要输出左括号时，无该元素或无元素，说明不匹配或右括号多了
else if (rightRecord.empty() || i != rightRecord.top()) return false;
else rightRecord.pop();
}
//栈不为空，说明左括号多了
return rightRecord.empty();
} 不论括号是分段的，例如()[]{[]}有三段 ；还是括号只有囊括的，例如{[()]}只有一段。有效的字符串每一段对应的栈一定可以被清空。
另一个技巧是进栈右括号而非进栈左括号，这样只需要比较迭代元素i和栈顶元素是否一致即可。
150. 逆波兰表达式求值 void GetTwoValues(stack& s, int& tempA, int& tempB) {
tempB = s.top();
s.pop();
tempA = s.top();
s.pop();
}
int evalRPN(vector& tokens) {
stack s;
int tempA;
int tempB;
for (auto i : tokens) {
if (i == "+") {
GetTwoValues(s, tempA, tempB);
s.push(tempA + tempB);
}
else if (i == "-") {
GetTwoValues(s, tempA, tempB);
s.push(tempA - tempB);
}
else if (i == "*") {
GetTwoValues(s, tempA, tempB);
s.push(tempA * tempB);
}
else if (i == "/") {
GetTwoValues(s, tempA, tempB);
s.push(tempA / tempB);
}
else {
s.push(stoi(i));
}
}
return s.top();
} 后缀表达式适合用栈 *** 作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。逆波兰表达式相当于是二叉树中的后序遍历。
71. 简化路径string simplifyPath(string path) {
stack simplePath;
// 字符串末尾添加一个/用于处理最后一级目录
path += '/';
for (auto str : path) {
// 每次遇到/时进行判断和 *** 作
if (str == '/' && !simplePath.empty()) {
// 两个目录名之间必须只有一个斜杠 '/'
if (simplePath.top() == '/') {
while (!simplePath.empty() && simplePath.top() == '/') {
simplePath.pop();
}
}
else if (simplePath.top() == '.') {
simplePath.pop();
// 一个点（.）表示当前目录本身
if (simplePath.top() == '/') {
simplePath.pop();
}
// 两个点 （..） 表示将目录切换到上一级
else if (simplePath.top() == '.') {
simplePath.pop();
// 需要返回上级目录的情况
if (simplePath.top() == '/') {
// 删除/..的/
simplePath.pop();
// 若存在上级目录，删除上级目录名以及/
if (!simplePath.empty()) {
while (simplePath.top() != '/') {
simplePath.pop();
}
simplePath.pop();
}
}
// 多个.表示的是文件名
else {
simplePath.push('.');
simplePath.push('.');
}
}
// 其余情况.也表示文件名
else {
simplePath.push('.');
}
}
}
simplePath.push(str);
}
// 最后一个目录名（如果存在）不能 以 '/' 结尾
if (!simplePath.empty() && simplePath.top() == '/' && simplePath.size() != 1) {
simplePath.pop();
}
string res;
while (!simplePath.empty()) {
res += simplePath.top();
simplePath.pop();
}
reverse(res.begin(), res.end());
return res;
} 每种情况都考虑清楚即可。本题采用方式是遇到“/”时再进行处理。
三、队列的应用 239. 滑动窗口最大值
//用deque实现单调队列
class MyQueue {
public:
//滑动窗口第一个值等于队列最大值是才出队，否则不进行 *** 作
void pop(int value) {
if (!this->m_queue.empty() && this->m_queue.front() == value) {
this->m_queue.pop_front();
}
}
//保持从头到尾由大到小
void push(int value) {
while (!this->m_queue.empty() && this->m_queue.back() < value) {
this->m_queue.pop_back();
}
this->m_queue.push_back(value);
}
int front() {
return this->m_queue.front();
}
private:
deque m_queue;
};
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
MyQueue mq;
vector res;
//前k-1个元素进入单调队列
for (int i = 0; i < k - 1; i++) {
mq.push(nums[i]);
}
//从0到size()-k+1次循环，先入队（窗口内含k个元素），然后输出结果，再出队（窗口内含k-1个元素）
for (int j = 0; j + k <= nums.size(); j++) {
mq.push(nums[j + k - 1]);
res.push_back(mq.front());
mq.pop(nums[j]);
}
return res;
}
}; 本题采用单调队列这种数据结构来完成，一次循环的过程如下图所示（来源：代码随想录）：
单调队列的队头元素存放滑动窗口内元素的最大值，并且队列递减排列，保证队头元素始终是可能的最大值。这样从0到size()-k+1次循环中，每次输出myQueue.front()即可。
实现单调队列的递减排列，并不是要将滑动窗口中的全部元素递减排列，而是在入队的过程中，只保留可能的最大元素：从deque的队尾入队，当待入队元素大于当前队尾时，deque()从队尾不断出队。
但这样会导致队列中的元素不足k个，因此在实现myQueue的pop() *** 作时，需要判断num[i]是否等于当前队头，只有等于时才执行deque的pop() *** 作。
单调队列不是一成不变的，针对不同场景要开发不同的写法。
四、优先队列 347.前 K 个高频元素
class MyCompare {
public:
bool operator()(const pair& lhs, const pair& rhs) {
return lhs.second > rhs.second;
}
};
class Solution {
public:
vector topKFrequent(vector& nums, int k) {
unordered_map freq;
for (auto num : nums) {
freq[num]++;
}
// 定义一个大小为k的小顶堆，用其扫描整个map
// priority_queue,Container为保存数据的容器
priority_queue, vector>, MyCompare> priQueue;
for (unordered_map::iterator it = freq.begin(); it != freq.end(); it++) {
priQueue.push(*it);
// 元素数量大于k时，出队元素为最小元素
if (priQueue.size() > k) {
priQueue.pop();
}
}
// 结果数组从大到小排列
vector res;
for (int i = k - 1; i >= 0; i--) {
res.push_back(priQueue.top().first);
priQueue.pop();
}
return res;
}
}; 首先，可以很自然地想到用map来统计频率，由于不需要对键值排序，此处采用unorder_map。
要对map中的频率值排序，此处采用堆排序，实现方法是优先队列（小顶堆/大顶堆）。
大顶堆：每个结点的值都大于或等于其左右孩子结点的值。
小顶堆：每个结点的值都小于或等于其左右孩子结点的值。
如果是排序，求升序用大顶堆，求降序用小顶堆。
而对于topK问题，最大的 K 个：小顶堆；最小的 K 个：大顶堆。因为只保留K个元素，而优先队列每次出队队头元素，若采用大顶堆，保留的是最小的K个元素；采用小顶堆则保留了最大的K个元素。利用仿函数可以改变优先队列的排序方式。
该算法的时间复杂度为O(nlog(k))，尤其注意排序过程中的时间复杂度为O(log(k))。
树结构和STL相关知识还要继续学习。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）