潍坊住房和城乡建设厅网站,辛集建设局网站,假发外贸网站模板,什么是网站交互性目录
1. 删除字符串中的所有相邻重复项#xff08;简单#xff09;
2. 逆波兰表达式#xff08;中等#xff09;
3. 基本计算器 II#xff08;中等#xff09;
4. 字符串解码#xff08;中等#xff09;
5. 验证栈序列#xff08;中等#xff09;
6. 小行星碰撞…目录
1. 删除字符串中的所有相邻重复项简单
2. 逆波兰表达式中等
3. 基本计算器 II中等
4. 字符串解码中等
5. 验证栈序列中等
6. 小行星碰撞中等
单调栈
1. 每日温度中等
2. 柱状图中最大的矩形困难
3. 最大矩形困难 1. 删除字符串中的所有相邻重复项简单 class Solution {
public:string removeDuplicates(string s) {string ans; // 字符串模拟栈这样可以直接输出答案不用把栈转成字符串for (auto ch : s){if (!ans.empty() ch ans.back()){ans.pop_back(); // 出栈}else{ans ch; // 入栈}}return ans;}
};
2. 逆波兰表达式中等
遍历字符串数组
如果遇到操作数将操作数入栈如果遇到运算符将两个操作数出栈其中先出栈的是右操作数后出栈的是左操作数然后计算然后将计算结果入栈
遍历完字符串数组后栈中只有一个元素就是逆波兰表达式的值。
class Solution {
public:int evalRPN(vectorstring tokens) {stackint st;for (auto s : tokens){if (s || s - || s * || s /){int right st.top();st.pop();int left st.top();st.pop();st.push(calculate(left, right, s[0]));}else{st.push(stoi(s));}}return st.top();
}private:int calculate(int left, int right, char op){switch (op){case :return left right;case -:return left - right;case *:return left * right;case /:return left / right;default:return 0;}}
};
3. 基本计算器 II中等
先计算乘除后计算加减
当一个数前面是 时该数入栈当一个数前面是 - 时该数的相反数入栈当一个数前面是 * / 时将该数与栈顶元素进行计算并将栈顶元素替换为计算结果
遍历完字符串后栈中所有元素的和就是表达式的值。
class Solution {
public:int calculate(string s) {vectorint st; // 数组模拟栈方便最后计算栈中所有元素的和int n s.size();int i 0;char op ;while (i n){if (s[i] ){i;}else if (s[i] 0 s[i] 9){// 将数字提取出来int num 0;while (i n s[i] 0 s[i] 9){num num * 10 (s[i] - 0);}if (op ){st.push_back(num);}else if (op -){st.push_back(-num);}else if (op *){st.back() * num;}else{st.back() / num;}}else{op s[i];i;}}// 计算栈中所有元素的和int ans 0;for (auto e : st){ans e;}return ans;}
};
4. 字符串解码中等 class Solution {
public:string decodeString(string s) {stackint nums; // 数字栈stackstring strs; // 字符串栈strs.push();int n s.size();int i 0;while (i n){if (s[i] 0 s[i] 9){// 将数字提取出来int num 0;while (i n s[i] 0 s[i] 9){num num * 10 (s[i] - 0);}// 将数字压入数字栈nums.push(num);}else if (s[i] [){// 将[后面的字符串提取出来i;string str;while (i n s[i] a s[i] z){str s[i];}// 将字符串压入字符串栈strs.push(str);}else if (s[i] ]){// 遇到]时数字栈栈顶k和字符串栈栈顶s是对应的即s重复了k次// 将数字栈栈顶和字符串栈栈顶都出栈// 将s重复了k次后的字符串追加到现在的字符串栈栈顶int k nums.top();nums.pop();string str strs.top();strs.pop();while (k--){strs.top() str;}i;}else{// 将单独的字符串不是[后面的字符串提取出来string str;while (i n s[i] a s[i] z){str s[i];}// 将字符串追加到字符串栈栈顶strs.top() str;}}return strs.top();}
};
5. 验证栈序列中等
遍历数组pushed将pushed的每个元素依次入栈每次将pushed的元素入栈之后如果栈不为空且栈顶元素与popped的当前元素相同则将栈顶元素出栈同时遍历数组popped直到栈为空或栈顶元素与popped的当前元素不同。
遍历数组pushed结束之后每个元素都按照数组pushed的顺序入栈一次。如果栈为空则每个元素都按照数组popped的顺序出栈返回true。如果栈不为空则元素不能按照数组popped的顺序出栈返回false。
class Solution {
public:bool validateStackSequences(vectorint pushed, vectorint popped) {stackint st;int i 0; // 用来遍历poppedfor (auto e : pushed){st.push(e);while (!st.empty() st.top() popped[i]){st.pop();i;}}return st.empty();}
};
6. 小行星碰撞中等
使用栈模拟小行星碰撞。
遍历小行星数组asteroids当遍历到小行星e时使用变量alive记录小行星e是否还存在即未爆炸。
当小行星e存在且e 0栈非空且栈顶元素 0时说明两个小行星相互向对方移动
先看e是否存在栈顶元素 -ee存在栈顶元素 -ee爆炸。再看栈顶元素是否存在如果栈顶元素 -e则栈顶元素爆炸执行出栈操作。
重复以上判断直到不满足条件如果最后alive为真说明小行星e不会爆炸则将e入栈。
class Solution {
public:vectorint asteroidCollision(vectorint asteroids) { vectorint st; // 数组模拟栈这样可以直接输出答案不用把栈转成数组for (auto e : asteroids){bool alive true;while (alive e 0 !st.empty() st.back() 0){alive st.back() -e; // e 是否存在if (st.back() -e){ st.pop_back();}}if (alive){st.push_back(e);}}return st;}
};
单调栈
1. 每日温度中等
可以维护一个存储下标的单调栈从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里则表示尚未找到下一次温度更高的下标。
遍历温度数组如果栈不空且当前温度 栈顶对应的温度那么就能知道栈顶那一天下一个更高温度出现在几天后将栈顶出栈循环操作直到不满足“栈不空且当前温度 栈顶对应的温度”的条件此时将当前下标入栈。
遍历完温度数组后留在栈中的下标就是气温在这之后都不会升高不用手动把其在答案数组对应的数置为0因为最开始数组默认用0初始化。
class Solution {
public:vectorint dailyTemperatures(vectorint temperatures) {stackint st; // 单调栈int n temperatures.size();vectorint ans(n);for (int i 0; i n; i){while (!st.empty() temperatures[i] temperatures[st.top()]){int index st.top();ans[index] i - index;st.pop();}st.push(i);}return ans;}
};
2. 柱状图中最大的矩形困难
以某根柱子为顶的最大矩形一定是从该柱子向两侧延伸直到遇到比它矮的柱子。
创建一个递增栈遍历高度数组如果当前高度 栈顶元素入栈否则栈顶出栈并计算以栈顶的柱子为顶的最大矩形面积。由于保存在栈中的柱子的高度是递增排序的因此栈中位于栈顶前面的一根柱子一定比位于栈顶的柱子矮于是很容易就能找到位于栈顶的柱子两侧比它矮的柱子。
class Solution {
public:int largestRectangleArea(vectorint heights) {int n heights.size();stackint st; // 递增栈st.push(-1);int ans 0;for (int i 0; i n; i){while (st.top() ! -1 heights[st.top()] heights[i]){int height heights[st.top()];st.pop();int width i - st.top() - 1;ans max(ans, height * width);}st.push(i);}while (st.top() ! -1){int height heights[st.top()];st.pop();int width n - st.top() - 1;ans max(ans, height * width);}return ans;}
};
3. 最大矩形困难
将矩阵中上下相邻的值为1的格子看成柱状图中的柱子。假设矩阵有m行n列以矩阵的每行为基线就可以得到m个柱状图然后就可以计算并比较每个柱状图中的最大矩形。
class Solution {
public:int maximalRectangle(vectorvectorchar matrix) {int m matrix.size(); // 行int n matrix[0].size(); // 列vectorint heights(n, 0);int ans 0;for (int i 0; i m; i){for (int j 0; j n; j){if (matrix[i][j] 0){heights[j] 0;}else{heights[j];}}ans max(ans, largestRectangleArea(heights));}return ans;}private:int largestRectangleArea(vectorint heights) {int n heights.size();stackint st; // 递增栈st.push(-1);int ans 0;for (int i 0; i n; i){while (st.top() ! -1 heights[st.top()] heights[i]){int height heights[st.top()];st.pop();int width i - st.top() - 1;ans max(ans, height * width);}st.push(i);}while (st.top() ! -1){int height heights[st.top()];st.pop();int width n - st.top() - 1;ans max(ans, height * width);}return ans;}
};
