文章目录

71.简化路径问题描述思路代码 150.逆波兰表达式求值问题描述思路代码 173.二叉搜索树迭代器问题描述思路代码 402.移掉K位数字问题描述思路代码 496.下一个更大的元素Ⅰ问题描述思路代码 503.下一个更大的元素Ⅱ问题描述思路代码 636.函数独占时间问题描述思路代码 735.行星碰撞问题描述思路代码 739.每日温度问题描述思路代码 901.股票价格跨度问题描述思路代码 921.使括号有效的最少添加问题描述思路代码 946.验证栈序列问题描述思路代码

71.简化路径

问题描述

思路

以斜杠分隔字符串，斜杠间的内容有目录名、空、单点、双点四种可能维护一个栈，顺序遍历斜杠间的内容，若为目录名则压入栈，若为双点且栈非空则弹出栈，其余两种情况不作处理

代码

string simplifyPath(string path) { vector<string>stack; string s; stringstream ss(path); while (getline(ss, s, '/')) { if (s == "..") { if (!stack.empty()) { stack.pop_back(); } continue; } if (s != ""&&s != ".") { stack.push_back(s); } } string result = ""; for (auto &x : stack) { result += ("/" + x); } return result.empty() ? "/" : result; }

150.逆波兰表达式求值

问题描述

思路

维护一个栈，顺序遍历波兰表达式，若为数字则压入栈，若为运算符则计算栈顶两个数字的结果，弹出两数字并压入计算结果

代码

int evalRPN(vector<string> &tokens) { int num; deque<int>stack; for (const auto &c : tokens) { if (c == "+" || c == "-" || c == "*" || c == "/") { switch (c[0]) { case '+': stack[stack.size() - 2] += stack.back(); break; case '-': stack[stack.size() - 2] -= stack.back(); break; case '*': stack[stack.size() - 2] *= stack.back(); break; case '/': stack[stack.size() - 2] /= stack.back(); break; } stack.pop_back(); } else { stringstream ss(c); ss >> num; stack.push_back(num); } } return stack.front(); }

173.二叉搜索树迭代器

问题描述

思路

维护一个栈，保存节点指针。初始化时，从根节点开始迭代，将所有左节点压入栈中对所有压入栈中的节点来说，在其前压入的节点的值都较大，在其后压入的节点的值都较小注意到压入栈中的节点可能拥有的右子树，右子树中的值大于其根节点的值，但相对于栈中其它节点的大小关系不变综合上述三点，根据以下顺序遍历二叉树：二叉树=栈顶节点->该节点可能拥有的右子树->下一个栈顶节点

代码

class BSTIterator { public: stack<TreeNode *> s; BSTIterator(TreeNode *root) { PushTree(root); } bool hasNext() { return !s.empty(); } int next() { TreeNode *node = s.top(); s.pop(); PushTree(node->right); return node->val; } void PushTree(TreeNode *root) { while(root != nullptr) { s.push(root); root = root->left; } } };

402.移掉K位数字

问题描述

思路

维护一个栈，顺序遍历字符串，当栈非空、当前元素大于栈顶元素、尚未达到移出数量限制时，循环弹出栈顶元素，最后压入当前元素移出元素的数量限制可能有富余，例如对于“12345”，上述步骤不会移出任何元素，所以要在最后从栈顶弹出剩余数量的元素注意当前元素为’0’时，只要没有达到数量限制，栈中的元素可能全部被弹出。由于结果不能以‘0’开头，所以栈为空时不将‘0’压入栈

代码

string removeKdigits(string num, int k) { string result = ""; for (const auto &c : num) { while (!result.empty() && c < result.back() && k>0) { result.pop_back(); k--; } if (result.empty() && c == '0') { continue; } result.push_back(c); } if (k >= result.size()) { return "0"; } return string(result.begin(), result.end() - k); }

496.下一个更大的元素Ⅰ

问题描述

思路

维护一个栈，顺序遍历nums2，先循环弹出小于当前元素的元素，之后压入当前元素。被弹出元素的下一个更大元素即为当前元素

代码

vector<int> nextGreaterElement(vector<int> &findNums, vector<int> &nums) { unordered_map<int, int>list; vector<int>stack; vector<int>result; for (auto beg = nums.begin(); beg != nums.end(); ++beg) { while (!stack.empty() && (*beg) > stack.back()) { list[stack.back()] = *beg; stack.pop_back(); } stack.push_back(*beg); } for (const auto &x : findNums) { result.push_back(list.find(x) == list.end() ? -1 : list[x]); } return result; }

503.下一个更大的元素Ⅱ

问题描述

思路

类似于496，但有两点不同：

若单次遍历没有找到更大元素，可以再循环遍历一次，更大的元素可能出现在元素前面，所以将遍历改为两次即可该题只有一个输入，同时起到了496中findNums和nums的作用，意味着我们可以直接保存元素的索引而不必使用字典保存结果

代码

vector<int> nextGreaterElements(vector<int> &nums) { vector<int>result(nums.size(), -1); vector<pair<int,int>>value_Index; for (int n = 1; n <= 2 * nums.size(); n++) { int index = n > nums.size() ? (n - nums.size() - 1) : n - 1; while (!value_Index.empty() && nums[index] > value_Index.back().first) { result[value_Index.back().second] = nums[index]; value_Index.pop_back(); } if (result[index] == -1) { value_Index.push_back(pair<int, int>(nums[index], index)); } } return result; }

636.函数独占时间

问题描述

思路

维护一个栈，顺序遍历输入，每次遍历可以得到三个值：id、“start”或“end”、time，若为start，则将time压入栈，若为“end”，则结合time和栈顶元素可以计算出函数id的独占时间dt。要注意求出dt后，栈中的其他元素即其它函数的开始时间都要加上dt。

代码

vector<int> exclusiveTime(int n, vector<string> &logs) { int id, time, pos1, pos2; string temp, flag; vector<int>stack; vector<int>result(n, 0); for (const auto &s : logs) { pos1 = s.find(":"); pos2 = s.find(":", pos1 + 1); id = stoi(s.substr(0, pos1)); time = stoi(s.substr(pos2 + 1)); flag = s.substr(pos1 + 1, pos2 - pos1 - 1); if (flag == "end") { int dt = time - stack.back() + 1; result[id] += dt; stack.pop_back(); for (auto &x : stack) { x += dt; } } else { stack.push_back(time); } } return result; }

735.行星碰撞

问题描述

思路

只有当左侧行星向右运动同时右侧行星向左运动才会发生碰撞维护一个栈，遍历数组，左侧行星爆炸意味着弹出栈，右侧行星爆炸意味着不压入栈

代码

vector<int> asteroidCollision(vector<int> &asteroids) { vector<int>result; for (auto x : asteroids) { bool isExist = true; int weight_Right = abs(x); while (!result.empty() && result.back() > 0 && x < 0) { int &weight_Left = result.back(); if (weight_Left < weight_Right) { result.pop_back(); } else { if (weight_Left == weight_Right) { result.pop_back(); } isExist = false; break; } } if (isExist) { result.push_back(x); } } return result; }

739.每日温度

问题描述

思路

该题与496、503类似，区别在于496、503求的是更大元素的值，而该题求的是元素与更大元素间的索引差，所以我们在栈中额外保存索引，在弹出元素时即可求出索引差

代码

vector<int> dailyTemperatures(vector<int> &T) { vector<pair<int, int>>stack; vector<int>result(T.size(), 0); for (int n = 1; n <= T.size(); n++) { while (!stack.empty() && T[n - 1] > stack.back().second) { result[stack.back().first - 1] = n - stack.back().first; stack.pop_back(); } stack.push_back(pair<int, int>(n, T[n - 1])); } return result; }

901.股票价格跨度

问题描述

思路

对某一天的价格跨度，有两种情况：

这一天的价格小于前一天的价格，则当天的价格跨度只能为1这一天的价格大于或等于前一天的价格，则当天的价格跨度可以包含前一天的价格跨度，因为前一天的价格跨度中的价格都是小于或等于前一天的价格的

代码

class StockSpanner { public: StockSpanner() {} int next(int price) { int count = 1; while (!stack.empty() && price >= stack.back().first) { count += stack.back().second; stack.pop_back(); } stack.push_back(pair<int, int>(price, count)); return count; } private: vector<pair<int, int>>stack; };

921.使括号有效的最少添加

问题描述

思路

添加的括号有两种作用：

补全左括号对应的右括号补全右括号对应的左括号

注意当右括号位于左括号左侧时，它们自身不能抵消，需要分别补齐

综上，维护一个栈，顺序遍历输入，当元素为’(‘时，压入栈，当元素为’)'时，若栈为空，说明该右括号位于所有左括号左侧，令结果+1，若栈非空，两括号抵消，弹出栈顶元素。遍历完成后，令结果+栈的长度，即需要补齐的左括号个数

代码

int minAddToMakeValid(string S) { vector<char>stack; int result = 0; for (const auto&c : S) { if (c == '(') { stack.push_back(c); } else { if (stack.empty()) { result++; } else { stack.pop_back(); } } } return result + stack.size(); }

946.验证栈序列

问题描述

思路

当下一个要弹出的元素非空时，按以下顺序进行操作

若当前栈顶元素等于下一个要弹出的元素，则弹出元素否则若下一个要压入的元素非空，则压入元素否则返回false

注意给出的压入序列和弹出序列长度相等，所以当下一个要弹出的元素为空时，下一个要压入的元素必为空，直接返回true

代码

bool validateStackSequences(vector<int> &pushed, vector<int> &popped) { vector<int>stack; auto beg_Pushed = pushed.begin(), beg_Poped = popped.begin(); while (beg_Poped != popped.end()) { if (!stack.empty() && stack.back() == *beg_Poped) { ++beg_Poped; stack.pop_back(); } else if (beg_Pushed == pushed.end()) { return false; } else { stack.push_back(*beg_Pushed); ++beg_Pushed; } } return true; }