- 前言
- 一、练习题目
- 二、思路及题解
- 1. LC1441-用栈操作构建数组
- 2. LC1021-删除最外层的括号
- 3. LC1700-无法吃午餐的学生数量
- 4. LC1381-设计一个支持增量操作的栈
- 总结
前言
欢迎大家积极在评论区留言一起讨论交流，知无不言，言无不尽，共同进步。本文是 栈 专题，更多其他专题内容详见《LeetCode每月集训系列》
一、练习题目
| 题目链接 | 难度 | 备注 |
|---|---|---|
| 1441. 用栈操作构建数组 | ★☆☆☆☆ | |
| 1021. 删除最外层的括号 | ★☆☆☆☆ | |
| 1700. 无法吃午餐的学生数量 | ★☆☆☆☆ | |
| 1381. 设计一个支持增量操作的栈 | ★☆☆☆☆ |
方法一：正常操作
（1）创建一个栈用来构建目标数组，再创建一个容器用来记录操作；
（2）先默认将每个数字压入栈中，若该数字和目标数组同位置的数字不同，则弹出栈；
（3）若栈中数组长度与目标数组长度相同时，可以提前返回记录数据。
代码如下：
class Solution {
public:
vector buildArray(vector& target, int n) {
stack stk;
vector record;
for (int i = 0; i < n; i++) {
stk.push(i + 1);
record.push_back("Push");
if (stk.top() != target[stk.size() - 1]) {
stk.pop();
record.push_back("Pop");
}
if (stk.size() == target.size()) return record;
}
return record;
}
};
方法二：使用哈希表
（1）将目标数组映射到哈希表中，再创建一个容器用来记录操作；
（2）顺序遍历list，先记录压入栈；若不存在于哈希表中则再记录弹出栈；
（3）最后直接返回记录数据即可。
代码如下：
class Solution {
public:
vector buildArray(vector& target, int n) {
unordered_map hash;
vector ans;
for (int i = 0; i < target.size(); ++i) {
hash[target[i]] = 1; // 映射到哈希表中
}
for (int i = 1; i <= target[target.size() - 1]; ++i) {
ans.push_back("Push");
if (!hash[i]) {
ans.push_back("Pop");
}
}
return ans;
}
};
2. LC1021-删除最外层的括号
方法一：使用栈
（1）创建一个栈，当字符为左括号时入栈，遇到右括号时将栈顶的左括号出栈；
（2）创建一个空字符串，将非外层括号加入到其中；
（3）当字符为左括号且入栈前栈是非空的或当前字符为右括号且栈顶左括号出栈后栈是非空的这两种情况时为非外层括号。
代码如下：
class Solution {
public:
string removeOuterParentheses(string s) {
stack stk;
string ans;
for (char ch : s) {
if (ch == '(') {
if (!stk.empty()) ans += ch;
stk.push(ch);
} else {
stk.pop();
if (!stk.empty()) ans += ch;
}
}
return ans;
}
};
方法二：计数法
（1）定义一个计数器。当遇到左括号，计数器 +1 ，遇到右括号，计数器 −1 ；
（2）遇到左括号，且当前计数值大于 0 ，则属于有效的左括号。
（3）遇到右括号，且当前计数值大于 1 ，则属于有效的右括号。
// 示例一
当前的计数值: 0 1 0 1
( ) ( )
遍历后计数值: 1 0 1 0
// 示例二
当前的计数值: 0 1 2 1 2 1 0 1
( ( ) ( ) ) ( )
遍历后计数值: 1 2 1 2 1 0 1 0
代码如下：
class Solution {
public:
string removeOuterParentheses(string s) {
int count = 0;
string ans = "";
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '(' && count++ > 0) ans.push_back(s[i]);
else if (s[i] == ')' && count-- > 1) ans.push_back(s[i]);
}
return ans;
}
};
3. LC1700-无法吃午餐的学生数量
方法一：取巧
（1）由于学生可以不断调整来领到喜欢的三明治形状，说明学生的顺序不重要，所以先统计出喜欢不同形状的学生数量；
（2）直至栈顶的三明治被领走后才可以拿到后面的三明治，说明三明治的顺序非常重要；
（3）按顺序遍历三明治，直到栈顶的三明治没有任何一位学生喜欢即可。
代码如下：
class Solution {
public:
int countStudents(vector& students, vector& sandwiches) {
int count[2] = {0};
for (int i = 0; i < students.size(); i++) {
count[students[i]]++; // 统计学生喜欢的形状树量
}
for (int i = 0; i < sandwiches.size(); i++) {
if (count[sandwiches[i]] > 0) count[sandwiches[i]]--;
else break;
}
return count[0] + count[1];
}
};
4. LC1381-设计一个支持增量操作的栈
方法一：使用数组模拟栈
（1）对于 push 操作，如果当前元素的个数没有达到上限，就把 栈顶位置 top 后移一个位置并添加一个元素；
（2）对于 pop 操作，若当前栈为非空，则返回栈顶元素，并将 top 前移一个位置，否则返回 −1 ；
（3）对于 inc 操作，直接对栈底最多 k 个元素加上 val 即可。
代码如下：
class CustomStack {
public:
vector stk;
int top;
CustomStack(int maxSize) {
stk.resize(maxSize);
top = -1;
}
void push(int x) {
if (top != stk.size() - 1) {
++top;
stk[top] = x;
}
}
int pop() {
if (top == -1) return -1;
--top;
return stk[top + 1];
}
void increment(int k, int val) {
for (int i = 0; i < min(k, top + 1); i++) {
stk[i] += val;
}
}
};
总结
题目难不要怕，只要每个月的每一天都坚持刷题学习，总有一天会熟练掌握的。欢迎加入【知识星球｜英雄算法联盟】与我们一同早起刷刷刷⛽️
