# 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. 最小栈
155. Min Stack
设计一个支持 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-solution
# 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
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. 滑动窗口最大值
239. Sliding Window Maximum
给你一个整数数组 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]
-
k
nums.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
中的元素单调递增,优先队列中包含了所有元素)
空间复杂度: ,这里仅考虑了优先队列所需空间,忽略了目标数组所需空间
参考
- 力扣官方题解:滑动窗口最大值
- cplusplus:std::priority_queue
# 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;
}
时间复杂度:,其中, 为数组长度
空间复杂度:,其中, 为窗口长度
- 队列最多有 个元素,故,队列所需空间为
- 忽略了目标数组所需空间
参考:
- 力扣官方题解:滑动窗口最大值
- 编程狂想曲:动画演示 单调队列 239. 滑动窗口最大值
- cplusplus:std::deque
# LeetCode 347. 前 K 个高频元素
347. Top K Frequent Elements
给你一个整数数组 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;
}
};
时间复杂度: ,其中, 为数组长度, 为输出高频元素数
- 遍历哈希表的最坏时间复杂度为
- 优先级队列的入队 / 出队时间复杂度为
空间复杂度:
参考:
- cplusplus:std::priority_queue
- 代码随想录:前 K 个高频元素
# LeetCode 394. 字符串解码
394. Decode String
给定一个经过编码的字符串,返回它解码后的字符串。
编码规则为: 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 <= 30
s
由小写英文字母、数字和方括号'[]'
组成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-solution
# LeetCode 85. 最大矩形
85. Maximal Rectangle
给定一个仅包含 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 的行数和列数
空间复杂度:
参考:leetcode-solution