# LeetCode 1047. 删除字符串中的所有相邻重复项
1047. Remove All Adjacent Duplicates In String
给出由小写字母组成的字符串 S ，重复项删除操作 会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例 1：
输入：s = "abbaca"
输出："ca"
解释：例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
示例 2：
输入：s = "azxxzy"
输出："ay"
提示：
-
s.length s仅由小写英文字母组成
# 思路
匹配问题 都是 栈 的强项
基本思路：遍历字符串，若当前字符与栈顶元素相等，将栈顶元素移除，否则，将字符压入栈中。遍历完字符串以后，栈内不再含有连续的重复字符，将栈内元素依次弹出、并填充到目标字符串即可
# Method 1: 栈
由于栈顶元素对应的是字符串的尾端，填充目标字符串时需按从右往左顺序填充
代码实现：
string removeDuplicates(string s) { | |
// 将字符依次压入栈，若遇连续相同字符，则将栈顶元素移除 | |
stack<int> stk; | |
for (auto c : s) { | |
if (!stk.empty() && c == stk.top()) stk.pop(); | |
else stk.push(c); | |
} | |
// 将栈内字符添加到新字符串中（最先出栈的放到字符串末尾） | |
int size = stk.size(); | |
string res(size, ' '); | |
for (int i = size - 1; i >= 0; i--) { | |
res[i] = stk.top(); | |
stk.pop(); | |
} | |
return res; | |
} |
时间复杂度：，其中， 为字符串长度
空间复杂度：，栈所需空间（这里没有把目标字符串所需空间考虑在内）
也可以将栈内元素按从左往右顺序填充到目标字符串，然后再对目标字符串进行翻转
# Method 2: 字符串
在 C++ 中，由于标准库类型 string 本身就提供了类似 入栈 和 出栈 的接口，可直接将目标字符串作为栈
代码实现：
string removeDuplicates(string s) { | |
string res = ""; | |
for (auto c : s) { // 从目标字符串尾部移除与 c 相同的字符 | |
if (!res.empty() && c == res.back()) | |
res.pop_back(); | |
else // 将字符 c 添加到目标字符串尾部 | |
res.push_back(c); | |
} | |
return res; | |
} |
时间复杂度：，其中， 为字符串长度
空间复杂度：，没有把目标字符串所需空间考虑在内
参考：
# LeetCode 150. 逆波兰表达式求值
LeetCode 150. Evaluate Reverse Polish Notation
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。 - 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是 向零截断 。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用 32 位 整数表示。
示例 1：
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：((2 + 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
提示：
-
tokens.length tokens[i]是一个算符 （"+"、"-"、"*"或"/"），或是在范围 内的一个整数
# 思路
逆波兰表达式，即，后缀表达式（运算符写在两个操作数的后面）
日常使用的是中缀表达式（运算符写在两个操作数的中间）
例如， 2 + 3 就是中缀表达式，对应的后缀表达式是 2 3 +
由此，本题的求解思路为：
-
定义一个 栈
-
遍历数组
tokens，若遇到的是数字，则将数字压入栈，若遇到的是"+"、"-"、"*"、"/"运算符，则从栈内取出两个数字进行计算，然后将计算结果压入栈中 -
遍历结束时，栈内剩余元素即为整个后缀表达式的计算结果
注意，数组 tokens 内的元素是 string 类型的对象，将 string 型的数字压入栈前需将其转换成 int 型
- 调用
stoi函数即可，参考 cplusplus：std::stoi
# Method: 栈
代码实现：
// 计算后缀表达式，并将结果压入栈 | |
void compute(stack<int> &stk, string c) { | |
int right = stk.top(); // 右操作数 | |
stk.pop(); | |
int left = stk.top(); // 左操作数 | |
stk.pop(); | |
if (c == "+") stk.push(left + right); | |
else if (c == "-") stk.push(left - right); | |
else if (c == "*") stk.push(left * right); | |
else if (c == "/") stk.push(left / right); | |
} | |
int evalRPN(vector<string>& tokens) { | |
stack<int> stk; | |
for (auto c : tokens) { | |
if (c == "+" || c == "-" || c == "*" || c == "/") | |
compute(stk, c); | |
else | |
stk.push(stoi(c)); // 将 string 类型转成 int 型 | |
} | |
int ans = stk.top(); | |
stk.pop(); | |
return ans; | |
} |
时间复杂度：，其中， 为 tokens 的长度
空间复杂度：，栈所需空间
# LeetCode 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.
提示：
-
val pop、top和getMin操作总是在 非空栈 上调用push、pop、top和getMin最多被调用 次
# Method: 辅助栈
算法思路：
定义一个元素栈（记作 stk），用于存储每个元素
定义一个辅助栈（记作 minStk），用于存储与每个元素对应的最小值（与元素值同步插入与删除）
-
当一个元素要入栈到 stk 时，我们取辅助栈 minStk 的栈顶元素与当前元素比较，将最小值插入辅助栈 minStk 中
-
当一个元素要从 stk 中弹出时，我们把辅助栈 minStk 的栈顶元素也相应弹出
-
在任意时刻，栈 stk 内的元素最小值就是辅助栈 minStk 的栈顶元素
代码实现：
class MinStack { | |
public: | |
stack<int> stk; | |
stack<int> minStk; // 辅助栈 | |
MinStack() { | |
minStk.push(INT_MAX); // 初始化辅助栈 | |
} | |
void push(int val) { | |
stk.push(val); | |
minStk.push(min(val, minStk.top())); | |
} | |
void pop() { | |
stk.pop(); | |
minStk.pop(); | |
} | |
int top() { | |
return stk.top(); | |
} | |
int getMin() { | |
return minStk.top(); | |
} | |
}; | |
/** | |
* Your MinStack object will be instantiated and called as such: | |
* MinStack* obj = new MinStack(); | |
* obj->push(val); | |
* obj->pop(); | |
* int param_3 = obj->top(); | |
* int param_4 = obj->getMin(); | |
*/ |
时间复杂度：入栈、出栈、获取栈顶元素、获取最小元素的时间复杂度均为
空间复杂度：，其中 为元素个数，考虑了辅助栈所需的额外空间
# LeetCode 20. 有效的括号
LeetCode 20. Valid Parentheses
给定一个只包括 '(' ， ')' ， '{' ， '}' ， '[' ， ']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
提示：
-
s.length s仅包含括号'()[]{}'
# 思路
从左往右遍历字符串时，后遇到的左括号需要先匹配，与栈后进先出的特点不谋而合
因此，括号匹配问题可以使用 栈 来解决
基本思路：遍历字符串，若遇到左括号，则将其入栈，若遇到右括号，则将对应栈顶左括号出栈
考察 括号不匹配 的三种情况：
- 存在多余的左括号：在这种情况下，待字符串遍历结束后，栈不为空
- 存在多余的右括号：字符串未遍历完，栈已经为空
- 括号没有多余，但是括号的方向不对应：在遍历字符串过程中，遍历到的右括号无法与栈顶左括号匹配
若字符串遍历结束后，栈为空，则说明括号全部匹配
# Method 1: 栈 + map
栈 存储的是 待匹配的左括号
哈希 map 用来存储可以匹配的括号类型，即：哈希表的 key 为右括号，value 为相同类型的左括号，这样查询 2 个括号是否对应只需 时间复杂度
具体可参考 力扣官方题解：有效的括号 和 Krahets：有效的括号
# Method 2: 栈
遍历字符串过程中，若遇到左括号，可将对应的右括号压入栈，后续遇到右括号时，只需将其与栈顶元素进行比较即可，若相等，则匹配，否则不匹配
即，栈 存储的是 与左括号对应的右括号
代码实现：
bool isValid(string s) { | |
if (s.size() % 2) return false; // 括号数为奇数，直接返回 false | |
stack<int> stk; | |
for (auto c : s) { // 范围 for | |
// 当 c 为 左括号 时，把对应的 右括号 压入栈 | |
if (c == '(') stk.push(')'); | |
else if (c == '[') stk.push(']'); | |
else if (c == '{') stk.push('}'); | |
// 当栈为空，或者，c 是 右括号 但 不等于栈顶元素，匹配失败 | |
else if (stk.empty() || c != stk.top()) return false; | |
//c 是 右括号 且 等于栈顶元素，匹配成功，从栈顶移除左括号 | |
else stk.pop(); | |
} | |
// 所有括号均已遍历完成，若栈为空，则匹配成功 | |
return stk.empty(); | |
} |
时间复杂度：，遍历字符串
空间复杂度：，栈所需空间
参考：代码随想录：有效的括号
# LeetCode 225. 用队列实现栈
LeetCode 225. Implement Stack using Queues
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（ push 、 top 、 pop 和 empty ）。
实现 MyStack 类：
void push(int x)将元素x压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
注意：
- 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
- 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列，只要是标准的队列操作即可。
示例 1：
输入
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出
[null, null, null, 2, 2, false]
Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False
提示：
-
x - 最多调用 100 次
push、pop、top和empty - 每次调用
pop和top都保证栈不为空
进阶： 你能否仅用一个队列来实现栈。
# 思路
栈 的特点是 后进先出 ，队列 的特点是 先进先出
可定义一个队列，使得 最先入栈的元素 放在 队首 ，最后入栈的元素 放在 队尾
-
对于入栈操作，只需将元素添加到队尾
-
对于出栈操作，需将队尾元素移除并返回
-
为获取栈顶元素，可先将栈顶元素出栈，并记录其值（本题定义的 出栈 函数具有返回值），然后再将其压入栈
-
判断栈是否为空，只需判断用来存储栈元素的队列是否为空
特别地，出栈操作可通过两个队列协同实现，也可仅用一个队列实现
# Method: 两个队列
定义队列 que1 ，用于存储 栈 的数据（ 最先入栈的元素 放在 队首 、最后入栈的元素 放在 队尾 ）
定义队列 que2 ，在 出栈 操作中，用于临时存放队列 que1 的前 que1.size() - 1 个元素，以便将 que1 队尾元素移除
时间复杂度：入栈操作 ，出栈操作 ，读取栈顶元素 ，判断栈是否为空 ，其中， 是元素个数
空间复杂度：
# Method: 一个队列
由于队列具有先进先出的特性，无需额外定义一个队列 que2 来实现 出栈 过程中元素的临时存放，即，直接将元素重新入队 que1 即可，这样就能使得最初的队尾元素出现在队首
代码实现：
class MyStack { | |
public: | |
queue<int> que; // 最先入栈的放在 que 队首，最后入栈的放在 que 队尾 | |
MyStack() { | |
} | |
void push(int x) { | |
que.push(x); | |
} | |
int pop() { | |
int length = que.size(); // 记录 que1 的长度，注意，不能直接将 que.size () 作为 for 循环的判定条件 | |
// 将 que 前 length - 1 个元素依次移出，然后放入队尾，使得最初的队尾元素出现在队首 | |
for (int i = 0; i < length - 1; i++) { | |
int temp = que.front(); | |
que.pop(); | |
que.push(temp); | |
} | |
// 记录最初的队尾元素值，并将其移除 | |
int ans = que.front(); | |
que.pop(); | |
return ans; | |
} | |
int top() { | |
int ans = pop(); // 复用已经定义的 MyStack 类别的 pop () 函数，将栈顶元素弹出 | |
push(ans); // 再将其压入栈 | |
return ans; | |
} | |
bool empty() { | |
return que.empty() ? true : false; | |
} | |
}; | |
/** | |
* Your MyStack object will be instantiated and called as such: | |
* MyStack* obj = new MyStack(); | |
* obj->push(x); | |
* int param_2 = obj->pop(); | |
* int param_3 = obj->top(); | |
* bool param_4 = obj->empty(); | |
*/ |
时间复杂度：入栈操作 ，出栈操作 ，读取栈顶元素 ，判断栈是否为空 ，其中， 是元素个数
空间复杂度：
事实上，也可以将 最后入栈的元素 放在 队首 、最先入栈的元素 放在 队尾 ，即，队列 的 前端 和 后端 分别对应 栈顶 和 栈底 。
但是，这种情况下的 入栈 操作则会复杂很多，对应的时间复杂度为 ，而 出栈 和 读取栈顶元素 则会简单很多，对应的时间复杂度为
可参考 力扣官方题解：用队列实现栈
# LeetCode 227. 基本计算器 II
给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值
整数除法仅保留整数部分
你可以假设给定的表达式总是有效的。所有中间结果将在 的范围内
注意：不允许使用任何将字符串作为数学表达式计算的内置函数（例如 eval() ）
示例 1：
输入：s = "3+2*2"
输出：7
示例 2：
输入：s = " 3/2 "
输出：1
示例 3：
输入：s = " 3+5 / 2 "
输出：5
提示：
- 1 <= s.length <= 3 * 105
- s 由整数和算符 (
'+','-','*','/') 组成，中间由一些 空格 隔开 - s 表示一个 有效表达式
- 表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
- 题目数据保证答案是一个 32-bit 整数
# Method: 栈
# 算法思路
由于乘除优先于加减计算，可以先进行所有乘除运算，并将这些乘除运算的结果放回原表达式的相应位置，最终，整个表达式的结果就等于一系列整数加减后的值
因此，可以用一个栈保存这些（进行乘除运算后的）整数的值
- 对于
'+'后面的数字，将其直接压入栈中 - 对于
'-'后面的数组，将其相反数压入栈中 - 对于
'*'或'/'后面的数字，可直接将其与栈顶元素计算，并使用计算结果替换栈顶元素
最后将栈中元素进行累加，即可得到字符串表达式的值
# 算法流程
定义 num 为当前处理的整数
定义变量 sign 为整数之前的运算符（将第一个数字之前的运算符视为加号）
遍历字符串 s
- 若当前字符
s[i]为数字字符，则更新当前整数值num：num = num * 10 + (s[i] - '0') - 若当前字符
s[i]为运算符或者字符串最后一个字符，则说明已经遍历到了整数num的末尾，此时需根据整数num之前的运算符sign对num进行处理：- 若
sign为'+'：将num压入栈； - 若
sign为'-'：将- num压入栈； - 若
sign为'*'或'/'：将其与栈顶元素计算，并将栈顶元素替换为计算结果
- 若
- 待处理
num后，更新sign为当前遍历到的运算符
最后，将栈中元素进行累加
这里可以用
vector数组模拟栈，以便最后计算栈中元素之和
# 代码实现
int calculate(string s) { | |
vector<int> stk; // 模拟栈 | |
int num = 0; // 当前处理的整数 | |
char sign = '+'; // 整数前面的运算符 | |
for (int i = 0; i < s.size(); ++i) { | |
// 遇到数字字符，计算对应的整数 | |
if (isdigit(s[i])) { | |
num = num * 10 + (s[i] - '0'); | |
} | |
// 遇到算术符或者字符串末尾，执行算术运算 | |
if ((!isdigit(s[i]) && !isspace(s[i])) || i == s.size() - 1) { | |
if (sign == '+') { | |
stk.push_back(num); | |
} else if (sign == '-') { | |
stk.push_back(-num); | |
} else if (sign == '*') { | |
stk.back() *= num; | |
} else if (sign == '/') { | |
stk.back() /= num; | |
} | |
sign = s[i]; // 更新 sign 为当前遍历到的运算符 | |
num = 0; // 重置整数 | |
} | |
} | |
int ans = 0; | |
for (int tmp : stk) ans += tmp; | |
return ans; | |
} |
# 复杂度分析
时间复杂度：，其中， 为字符串长度
空间复杂度：
# 参考资料
参考：
# LeetCode 232. 用栈实现队列
LeetCode 232. Implement Queue using Stacks
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（ push 、 pop 、 peek 、 empty ）：
实现 MyQueue 类：
void push(int x)将元素x推到队列的末尾int pop()从队列的开头移除并返回元素int peek()返回队列开头的元素boolean empty()如果队列为空，返回true；否则，返回false
说明：
- 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
- 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出
[null, null, null, 1, 1, false]
Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
提示：
-
x - 最多调用 100 次
push、pop、peek和empty - 假设所有操作都是有效的 （例如，一个空的队列不会调用
pop或者peek操作）
进阶： 你能否实现每个操作均摊时间复杂度为 的队列？换句话说，执行 个操作的总时间复杂度为 ，即使其中一个操作可能花费较长时间。
# 思路
栈具有后进先出的特性
若将一个栈的所有元素移入到另一个栈中，元素的排列顺序会变得与之前相反
# Method
解题思路：
-
定义两个栈，
stk1和stk2- 栈
stk1用来作为存储队列，即，最先入队的在stk1栈顶，最后入队的在stk1栈底 - 栈
stk2作为临时存储空间，用来协助实现队列的功能
- 栈
-
void push(int x)函数的实现：- 若
stk1非空：先将stk1内的所有元素都移出来，放进stk2，然后将x压入栈stk1，将stk2内的元素移回stk1 - 若
stk1为空，直接将x压入栈stk1即可
- 若
-
int pop()函数的实现：- 记录
stk1栈顶元素值，并弹出stk1栈顶元素，返回其值
- 记录
-
int peek()函数的实现：- 直接返回
stk1栈顶元素值即可
- 直接返回
-
bool empty()函数的实现：- 判断
stk1是否为空即可
- 判断
另，也可以 “将最先入队的放
stk1栈底，最后入队的在stk1栈顶” ，此时：入队操作可直接将x压入栈stk1；出队操作需将stk1栈底以上的元素全都临时存放到stk2，待stk1栈底元素弹出后，再将stk2所有元素移回stk1
代码实现：
class MyQueue { | |
public: | |
stack<int> stk1; | |
stack<int> stk2; | |
MyQueue() { | |
} | |
void push(int x) { | |
if (!stk1.empty()) { //stk1 非空 | |
while (!stk1.empty()) { // 将 stk1 元素压入栈 stk2 | |
stk2.push(stk1.top()); | |
stk1.pop(); | |
} | |
stk1.push(x); // 将 x 压入栈 stk1 | |
while (!stk2.empty()) { // 将 stk2 元素放回栈 stk1 | |
stk1.push(stk2.top()); | |
stk2.pop(); | |
} | |
} | |
else //stk1 为空，直接将 x 压入栈 stk1 | |
stk1.push(x); | |
} | |
int pop() { | |
int ans = stk1.top(); | |
stk1.pop(); | |
return ans; | |
} | |
int peek() { | |
int ans = stk1.top(); | |
return ans; | |
} | |
bool empty() { | |
if (stk1.empty()) return true; | |
return false; | |
} | |
}; | |
/** | |
* Your MyQueue object will be instantiated and called as such: | |
* MyQueue* obj = new MyQueue(); | |
* obj->push(x); | |
* int param_2 = obj->pop(); | |
* int param_3 = obj->peek(); | |
* bool param_4 = obj->empty(); | |
*/ |
注意，标准库实现的栈和队列，其成员函数 pop() 没有返回值，不能作为右值； top() 具有返回值，可以作为右值
另外，关于 peek() 函数的实现，可以直接调用已经定义了的 MyQueue 类别的 pop() 函数，即，通过函数的复用来实现。这样可以降低出错的可能性
# LeetCode 239. 滑动窗口最大值
给你一个整数数组 nums ，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1：
输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置 最大值
--------------- ------
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
-
nums.length -
nums[i] -
knums.length
# 思路：
数组长为 nums.size() ，窗口长为 k ，一共有 nums.size() - k + 1 个窗口
若采用暴力法，对每个窗口求最大值需要 的时间复杂度，则总时间复杂度为
针对本题的数据，暴力法会超时
本题有三种求解思路：可参考 力扣官方题解
- 优先队列（堆）
- 单调队列
- 分块 + 预处理
# Method 1: 优先队列
可以利用 最大化堆，即，根节点元素值最大的二叉堆， 来维护窗口的最大值
有关 最大化堆 ，可参考 优先级队列
算法流程：
-
定义一个 优先队列 ，其中，队列每个元素都是一个二元组，存储了
nums数组元素值和元素下标，即：priority_queue<pair<int, int>> que; -
将
nums数组的前k个元素（及下标）加入到优先队列中 -
遍历
nums数组元素下标i（从第k位元素开始），即，窗口的右边界- 将
(nums[i], i)加入到que中 - 若
que根节点所对应的数组元素下标（即，que.top().second） 小于 窗口的左边界（即，i - k + 1），则这个最大值不在窗口范围内，而是在窗口左侧，将其从que中移除 - 将
que根节点所对应的数组元素（即，que.top().first）加入到目标数组中
- 将
代码实现：
vector<int> maxSlidingWindow(vector<int>& nums, int k) { | |
priority_queue<pair<int, int>> que; | |
vector<int> res(nums.size() - k + 1, 0); | |
// 将前 k 个元素添加到优先队列 | |
for (int i = 0; i < k; i++) | |
que.emplace(nums[i], i); | |
// 将当前窗口最大值添加到目标数组 | |
res[0] = que.top().first; | |
for (int i = k; i < nums.size(); i++) { | |
// 将当前元素添加到优先队列 | |
que.emplace(nums[i], i); | |
// 当前队列的最大值不在窗口内，将其移除 | |
while (que.top().second < i - k + 1) | |
que.pop(); | |
// 将当前窗口最大值添加到目标数组 | |
res[i - k + 1] = que.top().first; | |
} | |
return res; | |
} |
时间复杂度： ，其中， 是数组 nums 的长度
- 遍历数组的时间复杂度为
- 将元素添加到优先队列的时间复杂度为 （在最坏情况下，数组
nums中的元素单调递增，优先队列中包含了所有元素）
空间复杂度： ，这里仅考虑了优先队列所需空间，忽略了目标数组所需空间
参考
# Method 2: 单调队列
双向队列：队列的两端都可以 入队 / 出队
单调队列：从队首到队尾，元素单调递减，或递增
本题可定义一个 元素单调递减的单调队列 ，以维护窗口内的最大值（即，队列的首端元素为队列最大值）
- 若队首元素不在窗口内（即，对应数组下标小于窗口左边界），将其移除
- 若队首元素在窗口内，则该元素即为窗口内元素的最大值
为实现队列元素的单调递减，我们在添加元素时，需做以下考虑：
- 若队列尾端元素小于等于当前元素，则将队尾元素移除（因为队尾元素对应的数组下标在当前元素的左侧，当队尾元素小于当前元素时，其不可能成为当前窗口及后续滑动窗口的最大值，可将其从队列中永久移除）
- 直到队列尾端元素大于当前元素时，才将当前元素添加到队列中
算法流程：
- 定义一个双向队列：
deque<int> que;，用以实现单调队列 - 遍历数组
nums数组元素下标，定义为窗口的右边界right- 若队列不为空且当前元素大于等于队尾元素，将队尾元素移除，直到队列为空或当前元素小于新的队尾元素
- 将当前元素添加到队尾
- 若队首元素的下标小于滑动窗口左侧边界，将其从队首移除，直到队首元素在窗口中为止
- 若长为
k的窗口已形成（即，right >= k - 1），则将窗口最大值（即，队首元素）添加到目标数组
特别地，为便于操作，我们可将数组元素的下标存放在队列中
代码实现：
vector<int> maxSlidingWindow(vector<int>& nums, int k) { | |
deque<int> que; // 单调队列（从队首到队尾，元素单调递减） | |
vector<int> res; // 目标数组 | |
for (int left = 0, right = 0; right < nums.size(); right++) { | |
// 队列不为空且当前考察元素大于等于队尾元素，将队尾元素移除 | |
while (!que.empty() && nums[que.back()] <= nums[right]) | |
que.pop_back(); | |
// 将当前元素的下标添加到队尾 | |
que.push_back(right); | |
// 窗口左边界 | |
left = right - k + 1; | |
// 将小于 left 的元素下标从队列移除 | |
while (que.front() < left) | |
que.pop_front(); | |
// 队列首端对应元素就是窗口最大值 | |
if (right >= k -1) | |
res.push_back(nums[que.front()]); | |
} | |
return res; | |
} |
时间复杂度：，其中， 为数组长度
空间复杂度：，其中， 为窗口长度
- 队列最多有 个元素，故，队列所需空间为
- 忽略了目标数组所需空间
参考：
# LeetCode 347. 前 K 个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1：
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
示例 2：
输入：nums = [1], k = 1
输出：[1]
提示：
-
nums.length k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 ，其中 是数组大小。
# 思路
解题基本思路：
- 统计元素出现频率：利用 哈希 map 来统计数组中各元素出现的次数
- 对频率排序：利用 优先级队列 来对频率进行排序
- 根据排序结果找出前 K 个高频元素
题目只需找出前 K 个高频元素，因此可采用固定大小为 K 的 优先级队列 维护一个长为 K 的有序序列即可，而无需采用 vector 容器对所有元素的频次进行排序
由于优先级队列（堆）只能移除队首元素，本题采用 最小化堆（小顶堆） ，以便移除频次最少的元素
最小化堆的定义：
class comp { | |
public: | |
bool operator() (const pair<int, int> &LHS, const pair<int, int> &RHS) { | |
return LHS.second > RHS.second; | |
} | |
}; | |
priority_queue<pair<int, int>, vector<pair<int, int>>, comp> que; |
对于堆，
LHS.second > RHS.second建立的是小顶堆，LHS.second < RHS.second建立的是大顶堆对于
sort函数，LHS.second > RHS.second得到的是降序排列，LHS.second < RHS.second得到的是升序排列
# Method: 哈希 map + 优先级队列
算法思路：
定义一个哈希表（ unordered_map ），用于统计数组元素的出现频次，其中，key 为元素值，value 为频次
定义一个优先级队列，遍历哈希表：
- 将哈希表的键值对添加到队列
- 若队列长度大于 K ，则从队列中移除频次最少的元素
从优先级队列中提取出前 K 个高频元素的元素值，将其填充到目标数组中
代码实现：
// 最小化堆的比较函数 | |
class comp { | |
public: | |
bool operator() (const pair<int, int> &LHS, const pair<int, int> &RHS) { | |
return LHS.second > RHS.second; | |
} | |
}; | |
class Solution { | |
public: | |
vector<int> topKFrequent(vector<int>& nums, int k) { | |
// 统计数字出现的频次 | |
unordered_map<int, int> hash; | |
for (int i = 0; i < nums.size(); i++) | |
hash[nums[i]]++; | |
// 利用固定大小为 K 的优先队列扫描哈希表 | |
priority_queue<pair<int, int>, vector<pair<int, int>>, comp> que; | |
for (auto it = hash.begin(); it != hash.end(); it++) { | |
que.push(*it); | |
if (que.size() > k) | |
que.pop(); | |
} | |
// 提取出前 K 个高频元素（升序填充到目标数组） | |
vector<int> res(k, 0); | |
for (int i = 0; i < k; i++) { | |
res[i] = que.top().first; | |
que.pop(); | |
} | |
return res; | |
} | |
}; |
时间复杂度： ，其中， 为数组长度， 为输出高频元素数
- 遍历哈希表的最坏时间复杂度为
- 优先级队列的入队 / 出队时间复杂度为
空间复杂度：
参考：
# LeetCode 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"
提示：
1 <= s.length <= 30s由小写英文字母、数字和方括号'[]'组成s保证是一个 有效 的输入s中所有整数的取值范围为
# Method 1: 栈
算法思路：
利用一个栈来维护字符串中的字母、数字和括号
遍历字符串 s ：
- 如果当前的字符为数位，解析出一个数字（连续的多个数位）并进栈
- 如果当前的字符为字母或者左括号，直接进栈
- 如果当前的字符为右括号，开始出栈，一直到左括号出栈，将出栈序列拼接成一个字符串；然后再取出栈顶的数字（即，字符串重复出现的次数），根据这个数字和字符串构造新字符串并进栈
为便于拼接目标字符串，可以用 vector 容器来模拟栈操作，具体可参考 leetcode-solution
代码实现：
string decodeString(string s) { | |
string res = ""; | |
stack<string> stk; | |
int ptr = 0; | |
while (ptr < s.size()) { | |
char cur = s[ptr]; | |
if (isdigit(cur)) { // 将数字（重复次数）入栈 | |
string digit = ""; | |
while (isdigit(s[ptr])) { // 解析数字 | |
digit.push_back(s[ptr]); | |
++ptr; | |
} | |
stk.push(digit); | |
} else if (isalpha(cur) || cur == '[') { // 将字母和左括号入栈 | |
stk.push(string(1, cur)); | |
++ptr; | |
} else { // 遇到右括号，将与之匹配的左括号及括号中间的字符出栈 | |
string tmp = ""; | |
while (stk.top() != "[") { // 解析当前括号对所包围的子串 | |
tmp += stk.top(); | |
stk.pop(); | |
} | |
stk.pop(); // 出栈：左括号 | |
int repNum = stoi(stk.top()); // 子串的重复次数 | |
stk.pop(); // 出栈：重复次数 | |
string str = ""; | |
while (repNum--) // 根据重复次数 repNum 和子串 tmp 解码字符串（例如，由 3 和 a 得到 aaa） | |
str += tmp; | |
if (stk.empty()) { // 无嵌套情形，可直接将 str 反转然后添加到目标字符串 | |
reverse(str.begin(), str.end()); | |
res += str; | |
} else { // 可能存在嵌套（例如 "3 [a2 [c]]"），或者前面有有效字符（例如 "2 [abc] ef3 [cd]"） | |
stk.push(str); | |
} | |
++ptr; | |
} | |
} | |
if (!stk.empty()) { // 连接栈内剩余元素，将其反转后添加到目标字符串 | |
string tmp = ""; | |
while (!stk.empty()) { | |
tmp += stk.top(); | |
stk.pop(); | |
} | |
reverse(tmp.begin(), tmp.end()); | |
res += tmp; | |
} | |
return res; | |
} |
时间复杂度：，其中 是原字符串 s 的长度， 是解码后得出的字符串 S 的长度
空间复杂度：
# Method 2: 递归
算法思路：
定义递归函数，从左向右解析字符串 s ：
- 如果当前位置为数字位，后面一定包含一个用方括号表示的字符串，此时可采取以下操作：
- 先解析出一个数字 repNum
- 然后解析左括号
- 递归解析后面的内容，遇到对应的右括号就返回，得到字母序列 str
- 根据字母序列 str 以及重复的次数 repNum 构造新的字符串
- 如果当前位置是字母位，可直接解析当前字母，然后递归解析后面内容
代码实现：
int getDigits(string& s, int& ptr) { // 从 ptr 位开始提取数字 | |
int num = 0; | |
while (ptr < s.size() && isdigit(s[ptr])) { | |
num = num * 10 + (s[ptr] - '0'); | |
++ptr; | |
} | |
return num; | |
} | |
string getString(string& s, int& ptr) { | |
if (ptr == s.size() || s[ptr] == ']') return ""; | |
string res = ""; | |
if (isdigit(s[ptr])) { | |
int repNum = getDigits(s, ptr); // 解析 Digits | |
++ptr; // 过滤左括号 | |
string str = getString(s, ptr); // 解析 String | |
++ptr; // 过滤右括号 | |
while (repNum--) res += str; // 构造目标字符串 | |
} else if (isalpha(s[ptr])) { | |
res = string(1, s[ptr]); // 解析 Char | |
++ptr; | |
} | |
return res + getString(s, ptr); | |
} | |
string decodeString(string s) { | |
int ptr = 0; | |
string ans = getString(s, ptr); | |
return ans; | |
} |
时间复杂度：，其中 是原字符串 s 的长度， 是解码后得出的字符串 S 的长度
空间复杂度：，只考虑递归使用的栈空间，不考虑答案所占空间
# LeetCode 85. 最大矩形
给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例 1：
输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6
解释：最大矩形如上图所示。
示例 2：
输入：matrix = [["0"]]
输出：0
示例 3：
输入：matrix = [["1"]]
输出：1
提示：
- rows == matrix.length
- cols == matrix[i].length
- 1 <= row, cols <= 200
- matrix [i][j] 为 '0' 或 '1'
# Method: 栈
算法思路：
可以将矩阵拆分成一系列的柱状图，为了计算矩形的最大面积，我们需要计算每个柱状图中的最大矩形面积，并从所有柱状图中找到全局最大值
定义 和 分别表示矩阵 matrix 的行数和列数，因此可将矩阵拆分成 个柱状图
特别地，第 i 个柱状图的范围为矩阵第 0 行至第 i 行，即，matrix [0] 至 matrix [i] ，在该柱状图中，第 j 个柱子的高度为 height [i][j]
- height [i][j] 表示从 (i, 0) 位置开始往下数、以 (i, j) 位置结尾的连续 1 的个数
其中，某柱状图中的最大矩形面积，可按照 LeetCode 84. 柱状图中最大的矩形 中的思路求解
通过遍历 i（即，遍历 个柱状图），求出每一个柱状图的最大矩形面积，即可得出所有柱状图中的最大矩形（即，矩阵中的最大矩形面积）
代码实现：
int maximalRectangle(vector<vector<char>>& matrix) { | |
int m = matrix.size(); | |
int n =matrix[0].size(); | |
// 预处理，计算每一个柱状图中的每一个柱子高度 | |
vector<vector<int>> height(m, vector<int>(n, 0)); | |
for (int i = 0; i < m; i++) { | |
for (int j = 0; j < n; j++) { | |
if (matrix[i][j] == '1') { | |
height[i][j] = i == 0 ? 1 : height[i - 1][j] + 1; | |
} | |
} | |
} | |
int ans = 0; // 矩阵中的最大矩形面积 | |
for (int i = 0; i < m; i++) { // 遍历 m 个柱状图，计算每个柱状图的最大矩形面积 | |
vector<int> left(n, -1); //left [j] 表示以 height [j] 为高的矩形的左边界 | |
vector<int> right(n, n); //right [j] 表示以 height [j] 为高的矩形的矩形的右边界 | |
stack<int> stk; // 单调栈 | |
for (int j = 0; j < n; j++) { // 维护单调栈，并更新 left 和 right 数组 | |
while (!stk.empty() && height[i][stk.top()] >= height[i][j]) { | |
right[stk.top()] = j; | |
stk.pop(); | |
} | |
if (!stk.empty()) left[j] = stk.top(); | |
stk.push(j); | |
} | |
int area = 0; // 第 i 个柱形图的最大矩形面积 | |
for (int j = 0; j < n; j++) { | |
area = max(area, height[i][j] * (right[j] - left[j] - 1)); | |
} | |
ans = max(ans, area); // 更新矩阵的最大矩形面积 | |
} | |
return ans; | |
} |
时间复杂度：，其中 和 分别为矩阵 matrix 的行数和列数
空间复杂度：
