第7章 栈与队列
queue有push(),pop()头删,back(),front(),empty(),size()
stack有push(),pop()尾删,top(),empty(),size()
两个特殊应用:单调队列,优先级队列
232. 用栈实现队列【简单】
思路:用栈模拟队列,就是两个栈里面的数据倒来倒去
class MyQueue { private: stack<int> in_stack, out_stack; //实现两个倒数的函数 void in2out() { while (!in_stack.empty()) { //in_stack非空 out_stack.push(in_stack.top()); in_stack.pop(); } } void out2in() { while (!out_stack.empty()) { in_stack.push(out_stack.top()); out_stack.pop(); } } public: MyQueue() {} void push(int x) { //入队 in_stack.push(x); } int pop() { //出队 即删除第一个入栈元素 in2out(); int x = out_stack.top(); out_stack.pop(); //即删除栈底部的数 out2in(); return x; } int peek() { //返回队列开头元素 即返回第一个入栈元素 in2out(); int x = out_stack.top(); out2in(); return x; } bool empty() { //判断队是否为空 return in_stack.empty(); } };
优化如下:官方版本
少了一些没必要的操作
class MyQueue { private: stack<int> inStack, outStack; void in2out() { while (!inStack.empty()) { outStack.push(inStack.top()); inStack.pop(); } } public: MyQueue() {} void push(int x) { inStack.push(x); } int pop() { if (outStack.empty()) { in2out(); } int x = outStack.top(); outStack.pop(); return x; } int peek() { if (outStack.empty()) { in2out(); } return outStack.top(); } bool empty() { return inStack.empty() && outStack.empty(); } };
225. 用队列实现栈【简单】
想到的方法:
//时间复杂度:删除是O(n),其余是O(1) //空间复杂度:O(1) class MyStack { private: queue<int> q_in, q_out; public: MyStack() {} void push(int x) { q_in.push(x); } int pop() { int temp = -1; while (!q_in.empty()) { temp = q_in.front(); q_in.pop(); if (!q_in.empty()) { q_out.push(temp); } } swap(q_in, q_out); return temp; } int top() { return q_in.back(); } bool empty() { return q_in.empty(); } };
官方代码如下:
//时间复杂度:入栈是O(n),其余是O(1) //空间复杂度:O(n) class MyStack { private: queue<int> queue1, queue2; public: MyStack() {} void push(int x) { queue2.push(x); while (!queue1.empty()) { queue2.push(queue1.front()); queue1.pop(); } swap(queue1, queue2); //交换后queue2为空 queue1中倒序 } int pop() { int r = queue1.front(); queue1.pop(); return r; } int top() { return queue1.front(); } bool empty() { return queue1.empty(); } };
思路二:使用一个栈
上一个代码的容器优化
class MyStack { private: queue<int> q; public: MyStack() {} void push(int x) { //主要思路是使得队列里面的元素倒序 int n = q.size(); q.push(x); for (int i = 0; i < n; i++) { q.push(q.front()); q.pop(); } } int pop() { int r = q.front(); q.pop(); return r; } int top() { return q.front(); } bool empty() { return q.empty(); } };
20. 有效的括号【简单】
思路:单调栈消消乐
时间复杂度:O(n)
空间复杂度:O(n+6);6是哈希表使用的空间;n表示字符串长度
class Solution { public: bool isValid(string s) { int n = s.size(); //获取字符串长度 if (n % 2 == 1) { //1.字符串长度为奇数肯定错误 return false; } stack<char> stk; unordered_map<char, char> pairs = { {')', '('}, {']', '['}, {'}', '{'} }; //列表初始化 for (int i = 0; i < s.size(); ++i) { if (s[i] == '(' || s[i] == '[' || s[i] == '{') { //2.存入左括号 stk.push(s[i]); } else { //3.消除右括号 if (stk.empty() || stk.top() != pairs[s[i]]) { return false; //false 空栈 或者 右括号与左括号类型不匹配 } stk.pop(); } } return stk.empty(); } };
1047. 删除字符串中的所有相邻重复项【简单】
正宗消消乐
注意:不要去写一个stack,string就有,只是用队列和栈的思路做题
class Solution { public: string removeDuplicates(string s) { string res; for (auto i : s) { if (!res.empty() && i == res.back()) { res.pop_back(); //尾删 } else { res += i; //尾插 } } return res; } };
150. 逆波兰表达式求值【中等】
class Solution { public: int evalRPN(vector<string>& tokens) { stack<string> s; for (auto i : tokens) { if (i == "+" || i == "-" || i == "*" || i == "/") { string temp2 = s.top(); s.pop(); int t2 = stoi(temp2); string temp1 = s.top(); s.pop(); int t1 = stoi(temp1); int res; if (i == "+") { res = t1 + t2; } else if (i == "-") { res = t1 - t2; } else if (i == "*") { res = t1 * t2; } else if (i == "/") { res = t1 / t2; } string r = to_string(res); s.push(r); } else{ s.push(i); } } return stoi(s.top()); } };
239. 滑动窗口最大值【困难,单调队列】
思路一:暴力破解
时间复杂度:O(n*k)
时间超时
class Solution { public: //暴力破解 int find_max(queue<int>q) { int q_max = INT_MIN; while (!q.empty()) { q_max = max(q_max, q.front()); q.pop(); } return q_max; } vector<int> maxSlidingWindow(vector<int>& nums, int k) { queue<int> q; vector<int> res; //1. 先做成第一个窗口 for (int i = 0; i < k; i++) { q.push(nums[i]); } res.push_back(find_max(q)); //2.滑动 for (int i = k; i < nums.size(); i++) { q.push(nums[i]); q.pop(); res.push_back(find_max(q)); } return res; } };
思路二:单调队列
相当于我们需要实现一个队列,这个队列呢,放进去窗口里的元素,然后随着窗口的移动,队列也一进一出,每次移动之后,队列告诉我们里面的最大值是什么。
维护元素单调递减的队列就叫做单调队列
C++中没有直接支持单调队列,需要我们自己来一个单调队列
时间复杂度:O(n)
空间复杂度:O(k)
class Solution { private: class MyQueue { //单调队列(从大到小) public: deque<int> que; // 使用deque双端数组来实现单调队列 // 每次弹出的时候,比较当前要弹出的数值是否等于队列出口元素的数值,如果相等则弹出。 // 同时pop之前判断队列当前是否为空。 void pop(int value) { if (!que.empty() && value == que.front()) { que.pop_front(); } } // 如果push的数值大于入口元素的数值,那么就将队列后端的数值弹出,直到push的数值小于等于队列入口元素的数值为止。 // 这样就保持了队列里的数值是单调从大到小的了。 void push(int value) { while (!que.empty() && value > que.back()) { que.pop_back(); } que.push_back(value); } // 查询当前队列里的最大值 直接返回队列前端也就是front就可以了。 int front() { return que.front(); } }; public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { MyQueue que; vector<int> result; for (int i = 0; i < k; i++) { // 先将前k的元素放进队列 que.push(nums[i]); } result.push_back(que.front()); // result 记录前k的元素的最大值 for (int i = k; i < nums.size(); i++) { que.pop(nums[i - k]); // 滑动窗口移除最前面元素 que.push(nums[i]); // 滑动窗口前加入最后面的元素 result.push_back(que.front()); // 记录对应的最大值 } return result; } };
思路三:优先队列
//优先队列 //时间复杂度:O(nlogn) 大根堆的删除头元素 //空间复杂度:O(n) class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { priority_queue<pair<int, int>> q; //默认为大根堆 头元素为最大值 for (int i = 0; i < k; ++i) { q.emplace(nums[i], i); } vector<int> ans = { q.top().first }; for (int i = k; i < nums.size(); ++i) { q.emplace(nums[i], i); while (q.top().second <= i - k) { //头元素索引不在滑动窗口内 q.pop(); } ans.push_back(q.top().first); } return ans; } };
347. 前 K 个高频元素【中等,优先级队列】
思路一:小根堆
涉及到优先级队列priority_queue,学完再来看
// 时间复杂度:O(nlogk) // 空间复杂度:O(n) class Solution { public: // 小顶堆 class mycomparison { public: bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) { return lhs.second > rhs.second; } }; vector<int> topKFrequent(vector<int>& nums, int k) { // 1. 要统计元素出现频率 unordered_map<int, int> map; for (auto i : nums) { map[i]++; } // 2. 对频率排序 // 定义一个小顶堆,大小为k priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que; // 3. 用固定大小为k的小顶堆,扫面所有频率的数值 for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) { pri_que.push(*it); if (pri_que.size() > k) { //频率低的排在前面 pri_que.pop(); //头删 } } // 4. 找出前K个高频元素,因为小顶堆先弹出的是最小的,所以倒叙来输出到数组 vector<int> result(k); for (int i = k - 1; i >= 0; i--) { result[i] = pri_que.top().first; pri_que.pop(); } return result; } };
思路二:自写sort排序;依据对组的second排序
下面写的sort有问题,学完排序再来补充,思路没问题
class Solution { public: bool cmp2(pair<int, int>&a, pair<int, int>&b) { return a.second > b.second; } vector<int> topKFrequent(vector<int>& nums, int k) { //1. 计数 unordered_map<int, int> map; for (auto& v : nums) { map[v]++; } //2. 换容器 vector<pair<int, int>> values; for (auto& kv : map) { values.push_back(kv); } //3.排序 sort(values.begin(), values.end(), cmp2); //4.输出 vector<int> res; for (int i = 0; i < k; i++) { res.push_back(values[i].first); } return res; } };
71. 简化路径【中等】
思路:
时间复杂度:O(n)
空间复杂度:O(n)
class Solution { public: string simplifyPath(string path) { vector<string> stk; //vector模拟栈 int n = path.size(), i = 0; string str = ""; //合成每个路径名 while (i < n) { if (path[i] == '/') { // 我们不处理/ ++i; } else { for (i; i < n && path[i] != '/'; ++i) { //合成文件名 str += path[i]; } if (str == ".") { //当前目录,什么都不做 } else if (str == "..") { //返回上级目录 if (!stk.empty()) { stk.pop_back(); } } else { //压入文件名 stk.push_back(str); } str = ""; //str置空 } } if (stk.empty()) //栈为空表示仍在根目录 return "/"; string ans = ""; for (auto& s : stk) ans += ('/' + s); //注意补'/' return ans; } };