栈/单调栈
1. 20. 有效的括号
简单
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1:
输入:s = "()"
输出:true
示例 2:
输入:s = "()[ ]{}"
输出:true
示例 3:
输入:s = "(]"
输出:false
示例 4:
输入:s = "([ ])"
输出:true
提示:
1 <= s.length <= 104
s
仅由括号'()[]{}'
组成
// 定义一个名为Solution的类,用于解决括号有效性问题。
class Solution {
public:
// 函数isValid用于检查输入的字符串s是否是有效的括号序列。
bool isValid(string s) {
// 定义一个字符栈st,用于存放预期的闭括号。
stack<char> st;// 获取输入字符串s的长度。
int n = s.size();// 遍历字符串s中的每个字符。
for(int i{}; i < n; ++i) {
// 如果当前字符是开括号'(',则将对应的闭括号')'推入栈中。
if(s[i] == '(') {
st.push(')');
} else if(s[i] == '[') {
// 如果当前字符是开括号'[',则将对应的闭括号']'推入栈中。
st.push(']');
} else if(s[i] == '{') {
// 如果当前字符是开括号'{',则将对应的闭括号'}'推入栈中。
st.push('}');
} else {
// 如果当前字符是闭括号,检查栈是否为空或者栈顶元素是否与当前闭括号匹配。
// 如果栈为空,或者栈顶元素与当前闭括号不匹配,则说明括号序列无效,返回false。
if(st.empty() || st.top() != s[i]) return false;// 如果栈顶元素与当前闭括号匹配,则弹出栈顶元素。
st.pop();
}
}// 遍历结束后,如果栈为空,则说明所有开括号都找到了匹配的闭括号,返回true。
// 如果栈不为空,则说明有未匹配的开括号,返回false。
return st.empty();
}
};
2. 155. 最小栈
中等
设计一个支持 push
,pop
,top
操作,并能在常数时间内检索到最小元素的栈。
实现 MinStack
类:
MinStack()
初始化堆栈对象。void push(int val)
将元素val推入堆栈。void pop()
删除堆栈顶部的元素。int top()
获取堆栈顶部的元素。int getMin()
获取堆栈中的最小元素。
示例 1:
输入: ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]]输出: [null,null,null,null,-3,null,0,-2]解释: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
提示:
-231 <= val <= 231 - 1
pop
、top
和getMin
操作总是在 非空栈 上调用push
,pop
,top
, andgetMin
最多被调用3 * 104
次
class MinStack {
public:
MinStack() {}
void push(int val) {
// 如果s2为空或者val小于等于s2的栈顶元素,则将val压入s2
if(s2.empty() || val <= s2.top()) s2.push(val);
// 将val压入s1
s1.push(val);
}
void pop() {
// 如果两个栈都为空,则直接返回
if(s1.empty() && s2.empty()) return;
// 如果s1的栈顶元素等于s2的栈顶元素,则也需要从s2中弹出元素
if(s1.top() == s2.top()) s2.pop();
// 从s1中弹出元素
s1.pop();
}
int top() {
// 如果s1为空,则返回-1表示栈为空
if(s1.empty()) return -1;
// 返回s1的栈顶元素
return s1.top();
}
int getMin() {
// 如果s2为空,则返回-1表示栈为空
if(s2.empty()) return -1;
// 返回s2的栈顶元素,即当前栈中的最小值
return s2.top();
}
private:
stack<int> s1;
stack<int> s2;
};
解释:
pop
方法中,返回空(null
)是因为pop
操作本身不返回任何值,它只是移除栈顶元素。如果栈为空,那么就没有元素可以移除,所以返回空表示没有操作发生。
top
方法:当s1
为空时,意味着栈中没有任何元素,因此没有栈顶元素可以返回。在这种情况下,返回-1作为一个标志值,表示栈为空。这是因为-1通常不会是一个合法的栈元素值,所以可以用作一个错误标志。
getMin
方法:同样,当s2
为空时,意味着没有最小值可以返回(因为栈中没有任何元素)。因此,返回-1作为一个标志值,表示栈为空。
3. 394. 字符串解码
中等
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: k[encoded_string]
,表示其中方括号内部的 encoded_string
正好重复 k
次。注意 k
保证为正整数。
你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k
,例如不会出现像 3a
或 2[4]
的输入。
示例 1:
输入:s = "3[a]2[bc]" 输出:"aaabcbc"
示例 2:
输入:s = "3[a2[c]]" 输出:"accaccacc"
示例 3:
输入:s = "2[abc]3[cd]ef" 输出:"abcabccdcdcdef"
示例 4:
输入:s = "abc3[cd]xyz" 输出:"abccdcdcdxyz"
提示:
1 <= s.length <= 30
s
由小写英文字母、数字和方括号'[]'
组成s
保证是一个 有效 的输入。s
中所有整数的取值范围为[1, 300]
class Solution {
public:
string decodeString(string s) {
string res = ""; // 用于构建最终的解码字符串
stack<int> nums; // 用于存储数字,这些数字表示重复的次数
stack<string> strs; // 用于存储字符串片段
int num = 0; // 用于记录当前读取的数字
int len = s.size(); // 字符串s的长度
for(int i = 0; i < len; ++i) {
if(s[i] >= '0' && s[i] <= '9') {
// 如果当前字符是数字,则累加到num中
num = num * 10 + s[i] - '0';
} else if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z')) {
// 如果当前字符是字母,则添加到res中
res = res + s[i];
} else if(s[i] == '[') {
// 如果遇到'[',则将之前的数字和字符串片段压栈
nums.push(num);
num = 0;
strs.push(res);
res = "";
} else {
// 如果遇到']',则进行解码操作
int times = nums.top();
nums.pop();
for(int j = 0; j < times; ++j)
strs.top() += res;
res = strs.top();
strs.pop();
}
}
return res; // 返回解码后的字符串
}
};
4. 739. 每日温度
中等
给定一个整数数组 temperatures
,表示每天的温度,返回一个数组 answer
,其中 answer[i]
是指对于第 i
天,下一个更高温度出现在几天后。如果气温在这之后都不会升高,请在该位置用 0
来代替。
示例 1:
输入: temperatures= [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]
示例 2:
输入: temperatures = [30,40,50,60] 输出: [1,1,1,0]
示例 3:
输入: temperatures = [30,60,90] 输出: [1,1,0]
提示:
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size(); // 获取温度数组的长度
vector<int> result(n, 0); // 初始化结果数组,所有元素都设置为0
stack<int> s; // 创建一个栈,用于存储索引
// 遍历每一天的温度
for (int i = 0; i < n; i++) {
// 当栈不为空,且当前温度大于栈顶元素对应的温度时
while (!s.empty() && temperatures[i] > temperatures[s.top()]) {
// 取出栈顶元素,即之前存储的索引
int index = s.top();
// 计算当前天与之前存储的天之间的天数差,并存储在结果数组中
result[index] = i - index;
// 从栈中移除栈顶元素
s.pop();
}
// 将当前天的索引压入栈中
s.push(i);
}
// 返回结果数组
return result;
}
};