skill-06-栈与队列
...大约 36 分钟
难度说明：🟢简单🟡中等🔴困难
学习资料
学习目标
- 掌握数据结构核心基础
- 借助数据结构完成常见题型
skill-06-栈与队列
理论基础
1.核心理论
- 栈：先进后出
- 队列：先进先出
2.技巧总结
- 掌握对栈、队列的理解
- 用栈实现队列：双栈思路（输入栈、输出栈，在输出栈为空的时候出发压栈）
- 用队列实现栈：双队列思路（头插法概念，一个队列queue1始终指向模拟栈的数据，另一个队列queue2作为辅助插入操作（新元素插入queue2，然后将queue1拼到其后，随后交换队列指向））
- 栈经典题目：
- 括号匹配问题、字符串去重问题：借助栈实现
- 括号匹配问题：左括号入栈，遇到右括号则匹配栈顶元素（右括号始终与其最近的左括号进行匹配，因此此处选用栈存储）
- 字符串去重问题：其思路和括号匹配问题类似，遍历元素，如果栈空或者与栈顶元素不匹配则说明不重复可入栈，如果遍历元素与栈顶元素相同说明重复则弹出top并继续下一个元素的遍历
- 逆序波兰表达式问题：操作数入栈，遇到操作符则从栈中取出两个操作数进行计算，然后将结果入栈，以此类推，直到所有元素遍历完成，最终栈中留存的就是操作结果
- 括号匹配问题、字符串去重问题：借助栈实现
- 队列经典题目
- 滑动窗口最大值问题
- 借助大顶堆维护可能成为窗口中的最大值的元素：初始化大顶堆（元素、索引对照），遍历元素（新元素入队，并判断当前堆顶元素索引idx和cur窗口左边界关系，如果满足idx<cur则弹出栈顶元素，直到窗口内的元素出现（idx>=cur），此时堆顶元素就是窗口最大值）
- 单调队列思路（todo）
- 前K问题：
- 前K个高频元素：统计+排序
- 选用堆排序思路，针对前K大有两种解题思路（大顶堆、小顶堆）优先队列
- 大顶堆（维护所有元素），最终弹出前K
- 小顶堆（维护K个元素），每次补充新元素时都和堆顶元素比较大小判断是否要进行置换（如果堆顶元素top<cur，则弹出top将较大的cur置换进来），当所有元素遍历完成，最终小顶堆中存储的就是前K大（优化空间复杂度，只需要占用K）
- 选用堆排序思路，针对前K大有两种解题思路（大顶堆、小顶堆）优先队列
- 前K个高频元素：统计+排序
- 滑动窗口最大值问题
常见题型
🟢232-用栈实现队列
1.题目内容
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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]
解释：
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
2.题解思路
👻方法1：双栈思路（输入栈、输出栈）
- 思路分析：构建双栈（输入栈
inputStack、输出栈outputStack）- 输入栈：正常
push数据 - 输出栈：从栈顶获取元素（当输出栈为空的时候，需要将输入栈中现存的数据依次弹出然后压入输出栈）==负负得正：压入输入栈的时候先进后出，当从输入栈中弹出压入输出栈时原
inputStack栈底的元素会被放到outputStack的栈顶，从而保证了输入的队列输出序列 - 压栈时机：此处的压栈指的是当输出栈为空的时候，需要将输入栈中现存的数据依次弹出然后压入输出栈，因此此处可以有两种压栈时机
push的时候❌：每次压入数据的时候，每次压入数据都倒一次或者限定outputStack为空则倒一次pop或peek的时候🟢：只在获取元素的时候当outputStack为空的时候进行压栈操作（只有当inputStack、outputStack不为空的时候整个队列才不为空）
empty：队列中的元素针对的是输入栈和输出栈的内容，由于优化处理选择的outputStack的压栈时机不同，所以不能进行校验输出栈是否为空（有可能此时输入栈不为空但还没压栈），所以队列不为空应该是两个栈都不为空的情况下才成立
- 输入栈：正常
/**
* 232 用栈实现队列
*/
class MyQueue2 {
// 双栈模拟
Stack<Integer> inputStack; // 输入栈
Stack<Integer> outputStack; // 输出栈
// 初始化
public MyQueue2() {
inputStack = new Stack<>();
outputStack = new Stack<>();
}
// 加入元素（往输入栈中插入）
public void push(int x) {
inputStack.push(x);
}
// 获取元素（从输出栈中获取，如果输出栈为空校验输入栈是否还有没遍历的数据，将输入栈现存数据压入输出栈）
public int pop() {
boolean isOutputStackEmpty = outputStack.isEmpty();
if (isOutputStackEmpty) {
// 输出栈为空，触发输入栈的压栈操作
while (!inputStack.isEmpty()) {
outputStack.push(inputStack.pop());
}
}
// 弹出栈顶元素
return outputStack.pop();
}
// 获取元素（不弹出元素）
public int peek() {
boolean isOutputStackEmpty = outputStack.isEmpty();
if (isOutputStackEmpty) {
// 输出栈为空，触发输入栈的压栈操作
while (!inputStack.isEmpty()) {
outputStack.push(inputStack.pop());
}
}
// 获取栈顶元素
return outputStack.peek();
}
// 队列为空判断
public boolean empty() {
// 当输入栈和输出栈都为空说明队列为空
return inputStack.isEmpty() && outputStack.isEmpty();
}
}
复杂度分析
时间复杂度：
push和empty为O（1），pop和peek为均摊 O(1)。对于每个元素，至多入栈和出栈各两次，故均摊复杂度为 O(1)空间复杂度：O(n)。其中 n 是操作总数。对于有 n 次 push 操作的情况，队列中会有 n 个元素，故空间复杂度为 O(n)
👻方法2：Deque（队列方法调用）
- 思路分析：借助Deque双端队列的操作方法实现
- 画图理解每个方法的执行效果，选用合适的方法组合实现栈或队列效果
/**
* 232 用栈实现队列
*/
class MyQueue1 {
// 双端队列模拟
Deque<Integer> deque ;
// 初始化
public MyQueue1() {
deque = new ArrayDeque<>();
}
// 加入元素
public void push(int x) {
deque.offerFirst(x);
}
public int pop() {
return deque.pollLast();
}
public int peek() {
return deque.peekLast();
}
public boolean empty() {
return deque.isEmpty();
}
}
复杂度分析
时间复杂度：
空间复杂度：
🟢225-用队列实现栈
1.题目内容
请你仅使用两个队列实现一个后入先出（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（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
2.题解思路
👻方法1：双队列（主队列(栈核心)、辅助队列头插）
- 思路分析：采用双队列的思路实现（queue1、queue2，类似头插的概念，每次将最新的数据插入到现有队列的头部：先插入queue2，然后将queue1的队列插入到queue2，最后交换queue1和queue2（相当于queue1每次保存了最新的"栈"数据，而queue2是作为头插的辅助））
/**
* 225 用队列实现栈（双队列、头插法思路）
*/
public class MyStack {
LinkedList<Integer> queue1; // queue1 保存最新的"模拟栈"数据
LinkedList<Integer> queue2; // queue2 作为头插的辅助队列
// 初始化
public MyStack() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
// 插入元素：类似头插概念
public void push(int x) {
// 1.将元素先插入到queue2
queue2.offer(x);
// 2.将queue1队列中现有元素依次补到queue2中，即确保最新插入的数据始终在队头（满足后入先出）
while(!queue1.isEmpty()){
queue2.offer(queue1.poll());
}
// 3.交换queue1、queue2，让queue1始终保存最新的"模拟栈"数据（即保存经过头插后的内容）
LinkedList<Integer> temp = queue1;
queue1 = queue2;
queue2 = temp;
// 交换两个队列指针（也可以直接让mainQueue指向tempQueue，然后tempQueue重置）
// mainQueue = tempQueue;
// tempQueue = new LinkedList<>();
}
// 弹出元素：从queue1中获取
public int pop() {
return queue1.poll();
}
// 返回栈顶元素：此处对应queue1最新头插的队首元素
public int top() {
return queue1.peek();
}
// 栈是否为空：queue1始终指向最新的模拟栈内容，因此此处只需要校验queue
public boolean empty() {
return queue1.isEmpty();
}
}
复杂度分析
- 时间复杂度：入栈操作 O(n)，其余操作都是 O(1)，其中 n 是栈内的元素个数。
- 入栈操作需要将 queue1中的 n 个元素出队，并入队 n+1 个元素到 queue2，共有 2n+1 次操作，每次出队和入队操作的时间复杂度都是 O(1)，因此入栈操作的时间复杂度是 O(n)
- 出栈操作对应将 queue1的队首元素出队，时间复杂度是 O(1)
- 获得栈顶元素操作对应获得 queue1 的队首元素，时间复杂度是 O(1)
- 判断栈是否为空操作只需要判断 queue1是否为空，时间复杂度是 O(1)
- 空间复杂度：O(n)，其中 n 是栈内的元素个数。需要使用两个队列存储栈内的元素
- 时间复杂度：入栈操作 O(n)，其余操作都是 O(1)，其中 n 是栈内的元素个数。
/**
* 用队列实现栈：双队列实现（基于头插概念）
*/
class MyStack {
public Queue<Integer> mainQueue; // 主队列：始终存储
public Queue<Integer> tempQueue; // 辅助队列：用于头插构建,临时存储元素
// 构造器
public MyStack() {
mainQueue = new LinkedList<>();
tempQueue = new LinkedList<>();
}
// 将元素x压入栈顶
public void push(int x) {
// 插入过程：将元素插入tempQueue，然后将mainQueue中的元素追加到tempQueue后面，随后交换两个队列，始终让mainQueue指向完整的元素列表（即栈）
tempQueue.offer(x);
while (!mainQueue.isEmpty()) {
tempQueue.offer(mainQueue.poll());
}
// 交换两个队列指针（也可以直接让mainQueue指向tempQueue，然后tempQueue重置）
mainQueue = tempQueue;
tempQueue = new LinkedList<>();
}
// 移除并返回栈顶元素
public int pop() {
// 返回并弹出mainQueue的队头元素（即对应头插后构成的栈的栈顶元素）
return mainQueue.poll();
}
// 返回栈顶元素
public int top() {
// 返回mainQueue的队头元素（即对应头插后构成的栈的栈顶元素）
return mainQueue.peek();
}
// 如果栈为空则返回true，否则返回false
public boolean empty() {
// 限定mainQueue即为对应的栈，因此此处只需要校验mainQueue是否为空
return mainQueue.isEmpty();
}
}
👻方法2：双端队列
- 思路分析：借助双端队列提供的队列方法实现栈操作
/**
* 225 用队列实现栈
*/
public class MyStack2 {
Deque<Integer> deque;
// 初始化
public MyStack2() {
deque = new LinkedList<>();
}
// 插入元素：
public void push(int x) {
deque.offerLast(x); // 队尾追加最新的元素
}
// 弹出元素：
public int pop() {
return deque.pollLast(); // 队尾获取最新的元素（满足LIFO）
}
// 返回栈顶元素：
public int top() {
return deque.peekLast();
}
// 栈是否为空：校验deque集合
public boolean empty() {
return deque.isEmpty();
}
}
复杂度分析
时间复杂度：
空间复杂度：
🟢020-有效的括号
1.题目内容
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
**输入：**s = "()"
**输出：**true
示例 2：
**输入：**s = "()[]{}"
**输出：**true
示例 3：
**输入：**s = "(]"
**输出：**false
示例 4：
**输入：**s = "([])"
**输出：**true
2.题解思路
👻方法1：替换法
- 思路分析：如果目标字符串中存在匹配的括号，则不断替换为空，当最终替换后的字符串为空时说明所有括号匹配，当不为空说明还存在不匹配的括号
/**
* 020 有效的括号
*/
public class Solution1 {
// 替换法
public boolean isValid(String s) {
// 当目标字符串存在匹配括号则不断进行替换
while(s.contains("{}") || s.contains("()") || s.contains("[]")){
// 替换匹配的括号
s = s.replace("{}","");
s = s.replace("()","");
s = s.replace("[]","");
}
// 替换操作结束后验证替换后的s是否为空（如果为空说明所有括号匹配，如果不为空说明还有括号没匹配）
return s.length()==0;
}
}
复杂度分析
时间复杂度：
空间复杂度：
另一种通用性写法：将指定的括号序列纳入集合进行判断（相当于基于上述思路修改，调整为更为通用的版本）
/**
* 🟢 020 有效的括号 - https://leetcode.cn/problems/valid-parentheses/description/
*/
public class Solution020_03 {
/**
* 限定字符串序列s只包括括号字符
* 思路分析：基于替换思路，如果存在范围内的括号对则不断替换为空
*/
public boolean isValid(String s) {
// 定义要校验的括号序列对
Set<String> strs = new HashSet() {
{
add("()");
add("[]");
add("{}");
}
};
// 如果s中存在括号对()\{}\[]则不断将其替换为空，最终得到空字符串则说明括号匹配，如果不为空则说明还有没匹配的括号
while (valid(strs, s)) {
// 替换指定范围内的括号对
for (String str : strs) {
s = s.replace(str, ""); // 替换
}
}
// 校验替换处理后的字符串序列
return "".equals(s);
}
// 校验指定字符串中是否包括括号序列
private boolean valid(Set<String> set, String s) {
for (String str : set) {
if (s.contains(str)) {
return true;
}
}
return false;
}
}
👻方法2：栈（遇到左括号入栈，遇到右括号匹配校验）
- 思路分析
- 为什么要用栈？：因为要优先匹配相近的左括号，因此后入的左括号优先与正向遍历的右括号进行匹配校验
- 核心：遇到左括号入栈，遇到右括号匹配校验（注意边界问题：stack为null的情况）
/**
* 020 有效的括号
*/
public class Solution2 {
// 栈：左括号入栈，碰到匹配的右括号则弹出（之所以选用栈是因为要优先匹配相近的左括号，因此后入的左括号优先与正向遍历的右括号进行匹配）
public boolean isValid(String s) {
// 定义括号字符匹配集合
Map<Character,Character> map = new HashMap<>();
map.put('}','{');
map.put(')','(');
map.put(']','[');
// 定义辅助栈
Stack<Character> stack = new Stack<>();
// 遍历目标字符串的字符序列，校验字符
for(char cur : s.toCharArray()){
if(map.containsValue(cur)){
// 如果是左括号则入栈（等待和右括号匹配）
stack.push(cur);
}else if(map.containsKey(cur)){
// 如果是右括号则从当前栈中弹出元素校验是否匹配（如果匹配则继续下一个位置判断，如果不匹配则直接返回false）
if(stack.isEmpty()){
return false; // 存在右括号，但是此时栈为空（说明没有匹配的左括号）
}else{
Character top = stack.pop();
if(!map.get(cur).equals(top)){
return false;
}
}
}
}
// 遍历结束，最终栈为空则说明完全匹配
return stack.isEmpty();
}
}
复杂度分析
时间复杂度：O（n）n 为目标字符串长度，需遍历整个字符串
空间复杂度：O（n）空间占用取决于栈空间占用（最坏情况下如果整个字符串为左括号）
/**
* 🟢 020 有效的括号 - https://leetcode.cn/problems/valid-parentheses/description/
*/
public class Solution020_01 {
/**
* 限定字符串序列s只包括括号字符
* 思路分析：基于栈思路（将左括号依次入栈，遇到右括号则取出最近的左括号进行匹配）
*/
public boolean isValid(String s) {
// 构建括号映射关系Map<右括号，左括号>
Map<Character, Character> map = new HashMap<>();
map.put(')', '(');
map.put('}', '{');
map.put(']', '[');
// 构建栈存储左括号
Stack<Character> stack = new Stack<>();
// 遍历字符串序列进行校验
for (char ch : s.toCharArray()) {
if (map.containsValue(ch)) {
// 如果是左括号，则直接入栈
stack.push(ch);
} else if (map.containsKey(ch)) {
// 如果是右括号，则从栈中取出元素进行校验
if (!stack.isEmpty()) {
if (map.get(ch).equals(stack.peek())) {
// 括号匹配，则弹出元素，继续进行校验
stack.pop();
} else {
return false; // 括号不匹配
}
} else {
// 如果栈为空，则说明当前字符无匹配的左括号
return false;
}
}
}
// 如果所有元素遍历完成，且最终stack为空，则说明括号完全匹配
return stack.isEmpty();
}
}
🟢1047-删除字符串中的所有相邻重复项
1.题目内容
给出由小写字母组成的字符串 s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 s 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例：
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
提示：
1 <= s.length <= 105s仅由小写英文字母组成。
2.题解思路
👻方法1：替换法（❌超时限制）
- 思路分析：定义重复集，校验
s是否包括重复集中的内容，包括则不断替换删除，直到不满足（这个思路和【20-有效的括号】的替换法解题思路类似，此处通过for循环简化分支代码）
/**
* 1047 删除字符串中的所有相邻重复项
*/
public class Solution1 {
// 替换法
public String removeDuplicates(String s) {
Set<String> set = new HashSet<>();
set.add("aa");
set.add("bb");
set.add("cc");
set.add("dd");
set.add("ee");
set.add("ff");
set.add("gg");
set.add("hh");
set.add("ii");
set.add("jj");
set.add("kk");
set.add("ll");
set.add("mm");
set.add("nn");
set.add("oo");
set.add("pp");
set.add("qq");
set.add("rr");
set.add("ss");
set.add("tt");
set.add("uu");
set.add("vv");
set.add("ww");
set.add("xx");
set.add("yy");
set.add("zz");
while (validRepeat(s, set)) { // 此处每次都要从set中进行全校验，一些重复字符串可能会重复出现，不能单纯用for控制
// 存在重复，则进行置换
for (String cur : set) {
if (s.contains(cur)) {
s = s.replace(cur, ""); // 删除重复出现的字符
}
}
}
// 返回结果
return s;
}
// 校验s中是否包括重复的字符序列
public boolean validRepeat(String s, Set<String> set) {
for (String cur : set) {
if (s.contains(cur)) {
return true;
}
}
return false;
}
}
复杂度分析
时间复杂度：
空间复杂度：
👻方法2：辅助栈
- 思路分析：借助辅助栈实现（
stack存放待比较的元素，遍历字符串中的每个字符：如果栈为空直接入栈，如果栈不为空则取出栈顶元素和当前遍历字符进行比较：top与cur匹配则出栈，否则继续入栈（注意此处不要复杂化实现，将其理解为括号匹配的做法））。最终字符串遍历完成，栈中留存的元素即为所得（需注意遍历顺序）- ==易错点：==此处简化为括号匹配的思路，判断栈顶元素的时候只需要判断相邻的两个字符是否为重复字符，可以理解为只要判断当前top元素是否和当前遍历元素重复，重复则直接移除top元素，不重复则继续补充元素。不要理解为类似
abbba这种形式下出现连续bbb就要把b全部消除，需注意的是每次比较都是两两比较，基于这种思路就可以转为括号匹配的思路去做（abbbaca=>abaca）
- ==易错点：==此处简化为括号匹配的思路，判断栈顶元素的时候只需要判断相邻的两个字符是否为重复字符，可以理解为只要判断当前top元素是否和当前遍历元素重复，重复则直接移除top元素，不重复则继续补充元素。不要理解为类似
/**
* 1047 删除字符串中的所有相邻重复项
*/
public class Solution2 {
/**
* 辅助栈：借助辅助栈存储元素
* 1.遍历指定元素，每次和栈顶元素进行比较，如果匹配说明出现重复，则直接弹出栈顶元素top
* 2.所有元素遍历完成，最终栈中留存的就是所得
*/
public String removeDuplicates(String s) {
// 定义辅助栈
Stack<Character> stack = new Stack<>();
// 遍历字符串序列
for (int i = 0; i < s.length(); i++) {
char cur = s.charAt(i);
if (stack.isEmpty()) {
stack.push(cur); // 元素入栈
} else {
// 判断和栈顶元素是否匹配，匹配则移除栈顶元素并继续遍历
char top = stack.peek();
if (top == cur) {
stack.pop(); // 弹出栈顶元素
} else {
stack.push(cur); // 元素入栈
}
}
}
// 栈中留存的元素即为所得
String res = "";
while (!stack.isEmpty()) {
res = stack.pop() + res; // 逆序存放
}
return res;
}
}
复杂度分析
时间复杂度：O（n）需遍历字符串序列
空间复杂度：O（n）需借助辅助栈存储待比较的元素
/**
* 🟢 1047 删除字符串中的所有相邻重复项
*/
public class Solution1047_01 {
// 辅助栈：构建辅助栈存储已遍历元素（出现重复则剔除）
public String removeDuplicates(String s) {
// 构建辅助栈存储遍历元素
Stack<Character> stack = new Stack<>();
for(char cur : s.toCharArray()){
/**
* 栈不为空时，比较栈顶元素与当前遍历元素
* - 如果相同说明出现了重复元素则弹出栈顶元素(此处需要消除重复的元素，因此重复元素不需要再次入栈)
* - 否则将cur元素入栈等待校验
*/
if(!stack.isEmpty() && stack.peek()==cur){
stack.pop();
}else{
stack.push(cur);
}
}
// 遍历完成，栈中留存的元素即为最终的字符串序列，需依次弹出并逆序输出
String res = new String();
while(!stack.isEmpty()){
res = stack.pop() + res;
}
// 返回结果
return res;
}
}
/**
* 🟢 1047 删除字符串中的所有相邻重复项 - https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
*/
public class Solution1047_01 {
/**
* 思路分析：构建栈辅助操作，将字符ch与栈顶元素top进行校验
* - 如果相同则说明出现连续重复则跳过
* - 如果不相同则说明不连续重复，可以将其加入栈
*/
public String removeDuplicates(String s) {
// 构建栈辅助遍历
Stack<Character> stack = new Stack<>();
for (char ch : s.toCharArray()) {
if (!stack.isEmpty()) {
// 比较当前栈顶元素和当前字符
if (ch != stack.peek()) {
stack.push(ch); // 字符不匹配，可继续入栈
} else {
/**
* stack.pop();在此处的设定，可结合调试分析
* abbaca => abaca (如果不弹出匹配的栈顶字符，则栈中至少会留下连续重复字符中的1个)
* abbaca => ca(弹出匹配的栈顶字符，则会将连续的字符一一消除)
*/
stack.pop(); // 字符匹配，弹出栈顶元素（此步将重复项本身也消除）
}
} else {
// 栈为空，没有比较项目，可直接加入
stack.push(ch);
}
}
// 返回栈中元素构建的字符串
StringBuffer res = new StringBuffer();
while (!stack.isEmpty()) {
res.insert(0, stack.pop());
}
// 返回结果
return res.toString();
}
}
👻方法3：StringBuffer模拟辅助栈
- 思路分析：借助指针和StringBuffer模拟辅助栈的操作，既保留了原有字符遍历的有序性，又使用top指针指向字符串尾部元素（配合模拟栈操作）
- 借助StringBuffer + top指针 模拟入栈、出栈操作，每次执行入栈、出栈操作需注意top指针的移动（top始终指向stack的尾部元素）
/**
* 1047 删除字符串中的所有相邻重复项
*/
public class Solution2 {
/**
* 辅助栈：借助辅助栈（StringBuffer+top指针）存储元素
* 1.遍历指定元素，每次和栈顶元素进行比较，如果匹配说明出现重复，则直接弹出栈顶元素top（每次入栈、出栈需要注意top指针的同步移动）
* 2.所有元素遍历完成，最终栈中留存的就是所得（即StringBuffer字符串）
*/
public String removeDuplicates(String s) {
// 定义Stringbuffer和top指针模拟辅助栈
StringBuffer stack = new StringBuffer();
int top = -1; // 初始化
for (int i = 0; i < s.length(); i++) {
char cur = s.charAt(i);
if (top == -1) {
stack.append(cur); // 栈为空直接加入数据
top++; // top 继续指向尾部元素
} else if (top != -1 && top < s.length()) {
// 栈不为空，判断top与cur是否匹配
char curTop = stack.charAt(top);
if (curTop == cur) {
// 存在匹配，执行出栈
stack.deleteCharAt(top);
top--; // 出栈 top--
} else {
// 不匹配，继续入栈
stack.append(cur);
top++; // 入栈 top++
}
}
}
// 返回结果
return stack.toString();
}
}
复杂度分析
时间复杂度：O（n）需遍历字符串数据
空间复杂度：O（n）借助StringBuffer+top指针模拟栈，此处空间复杂度主要考虑StringBuffer的空间占用，最坏情况下就是没有重复元素可删除
与辅助栈的思路类似，此处借助StringBuffer对象和top指针模拟栈操作，top指针始终指向最近加入的元素（栈顶），可以在保证数据遍历顺序的基础上还模拟了栈的特点，从而交换了【方法2】中的逆序输出的步骤
/**
* 🟢 1047 删除字符串中的所有相邻重复项
*/
public class Solution1047_02 {
// 借助StringBuffer模拟栈操作
public String removeDuplicates(String s) {
// 构建StringBuffer模拟栈操作
StringBuffer res = new StringBuffer();
int top = -1; // 定义top指针始终指向最后一个元素
for (char cur : s.toCharArray()) {
/**
* 栈不为空时，比较栈顶元素与当前遍历元素
* - 如果相同说明出现了重复元素则弹出栈顶元素(此处需要消除重复的元素，因此重复元素不需要再次入栈)
* - 否则将cur元素入栈等待校验
*/
if (top != -1 && res.charAt(top) == cur) {
res.deleteCharAt(top);
top--;
} else {
res.append(cur);
top++;
}
}
// 返回结果
return res.toString();
}
}
🟡150-逆波兰表达式求值
1.题目内容
给你一个字符串数组 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
2.题解思路
👻方法1：辅助栈
- 思路分析：
- 符号类型：操作数（整数类型）、操作符号（
+-*/）- 判断token类型的时候如果数字不好判断可以优先判断操作符（因此此处限定tokens类型为String，无法直接用Character的校验方法判断是否为字符，因此可以先判断操作符（穷举判断）），剩余的默认认为是数字即可
- 算法思路：借助辅助栈存放待处理的操作数，循环遍历
tokens，遇到操作数则直接入栈，遇到操作符号则从栈中取出两个操作数进行运算并将运算结果入栈。遍历结束，最终栈中存放的就是计算结果 - 案例分析：
["4","13","5","/","+"]4入栈（after stack:4）13入栈（after stack:4 13）5入栈（after stack:4 13 5）/从栈中取两个操作数：13（左操作数）/ 5（右操作数）= 2将结果2入栈（after stack:4 2）+从栈中取两个操作数：4（左操作数）+ 2（右操作数）= 6将结果6入栈（after stack:6）- 遍历完成，取出栈剩余的最后一个元素即为
res=6
- 符号类型：操作数（整数类型）、操作符号（
/**
* 150 逆序波兰表达式
*/
public class Solution1 {
// 辅助栈
public int evalRPN(String[] tokens) {
// 定义辅助栈存储操作数
Stack<Integer> stack = new Stack<>();
/**
* 遍历tokens，根据token类型决定操作
* 1.数字
* 2.计算符号+-×/
*/
for (String token : tokens) {
// 符号判断
if ("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token)) {
// 取出栈中的操作数进行操作，随后将操作结果入栈等待下一次运算
int right = stack.pop(); // 右操作数(后入先出)
int left = stack.pop(); // 左操作数
// 根据操作符进行运算
int res = -1;
switch (token) {
case "+": {
res = left + right;
break;
}
case "-": {
res = left - right;
break;
}
case "*": {
res = left * right;
break;
}
case "/": {
res = left / right;
break;
}
default: {
// 非指定操作符号
break;
}
}
// 将操作结果入栈
stack.push(res);
} else {
// 对于非操作符即为数字（如果给定的tokens正常的情况下）
stack.push(Integer.valueOf(token)); // 操作数入栈
}
}
// 最终栈中留存的元素即为res
return stack.pop();
}
}
复杂度分析
时间复杂度：O（n）n 为tokens数组长度
空间复杂度：O（n）空间复杂度取决于栈占用的空间
🔴239-滑动窗口最大值
1.题目内容
给你一个整数数组 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]
2.题解思路
👻方法1：暴力法-区间统计（❌超时限制）
- 思路分析：从起点开始遍历（确定每个区间【left，right】），每次都去计算一遍区间的最大值，然后存储
/**
* 239 滑动窗口的最大值
*/
public class Solution1 {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
// 1.定义数组存储滑动窗口的最大值
int[] maxArr = new int[len - k + 1]; // maxArr[i] 表示以i为起点的滑动窗口的最大值
// 2.暴力循环（确定窗口起点和终点，获取滑动窗口的最大值）
for (int i = 0; i < len - k + 1; i++) { // i 的临界取值受限于滑动窗口大小
// 统计区间的最大值
int curMax = Integer.MIN_VALUE;
for (int left = i; left < i + k; left++) {
curMax = Math.max(curMax, nums[left]); // 更新最大值
}
maxArr[i] = curMax; // 填充数组
}
// 返回结果集
return maxArr;
}
}
复杂度分析
时间复杂度：O（n2）（需遍历数组的同时还需计算滑动窗口的最大值）
空间复杂度：O（m） （m<n）构建辅助数组存储滑动窗口的最大值
/**
* 🔴 239 滑动窗口最大值 - https://leetcode.cn/problems/sliding-window-maximum/submissions/598655671/
*/
public class Solution239_01 {
/**
* 思路分析：模拟法（滑动窗口，计算每个窗口的最大值，封装结果）
*/
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
// 定义结果集
int[] res = new int[n - k + 1];
// int cur = 0; // 滑动窗口填充指针
// 遍历数组
for (int i = 0; i < n - k + 1; i++) { // i 的有效取值为[0,n-k]
// 滑动窗口有效取值[i,i+k-1]
res[i] = getMaxByRange(nums, i, i + k - 1);
}
// 返回结果集
return res;
}
// 计算指定数组范围中的max（即窗口内的max,取值限定[start,end]）
private int getMaxByRange(int[] nums, int start, int end) {
int max = Integer.MIN_VALUE;
for (int i = start; i <= end; i++) {
max = Math.max(max, nums[i]);
}
return max;
}
}
👻方法2：堆（优先队列）
- 思路分析：借助堆实时维护最大值（大顶堆可以实时维护一系列元素中的最大值）
- （1）大根堆定义：将数组元素和对应索引构建成数组，维护大根堆（数据元素不相等时优先按照元素大小排序，数据元素相等时优先按照索引大小排序）
- （2）初始化大根堆：初始化窗口（前k个元素入堆），此时初始化窗口的最大值对应的就是堆顶元素
- （3）遍历剩余元素，滑动窗口，更新最大值
cur为max数组当前填充位置（实际也可以理解为当前窗口的左边界，窗口的有效取值范围为[cur,cur+k-1]）每次遍历新的元素直接将其入堆，随后判断堆顶元素对应索引是否小于
cur（如果小于则表示这个堆顶元素已经是左边界左侧的内容了，已经划出了窗口，可以直接移除）- 如果小于则直接移除（
poll，除了此处移除，其他情况用peek查看元素），当堆顶元素（最大值出现在窗口内，则停止移出操作，此时堆顶元素对应为窗口的最大值）
- 如果小于则直接移除（
上述操作完成，此时堆顶元素对应的就是当前窗口的最大值
以此类推，遍历完所有元素，最终返回封装好的
max
- 注意点：此处需注意，窗口内的最大值可能会作为下一个窗口的最大值，因此不着急将其直接移除，top移除的条件限定在当top元素索引不在指定窗口范围内才触发移除，上述核心要点可以梳理如下：
- ① 定义大根堆：
<val,index>优先val（从大到小）、其次index（从小到大） - ② 初始化大根堆：前K个元素入堆，并初始化
res[0] - ③ 遍历剩余元素：纳新、排除、更新
res[cur]（窗口的有效取值范围为[cur,cur+k-1]）- a.纳新：将遍历元素加入
pq - b.排除：校验
top元素索引（top指向当前窗口的最大值，因此要校验其对应索引是否在窗口的限定范围内，如果不在则弹出） - c.更新：经过步骤b，此时top指向当前窗口有效取值范围的最大值，将其纳入结果集
- a.纳新：将遍历元素加入
- ① 定义大根堆：
/**
* 239 堆（优先队列）
*/
public class Solution2 {
public int[] maxSlidingWindow(int[] nums, int k) {
// 构建大顶堆（维护元素和对应索引位置）
int len = nums.length;
// 大根堆维护：{数组元素值,索引位置}
PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] item1, int[] item2) {
// 数据元素不相等时优先按照元素大小排序，数据元素相等时优先按照索引大小排序
return item1[0] != item2[0] ? item2[0] - item1[0] : item2[1] - item2[1];
}
});
// 封装大根堆元素(前K个元素进入)
for (int i = 0; i < k; i++) {
queue.offer(new int[]{nums[i], i});
}
int[] max = new int[len - k + 1]; // 初始化最大值结果集
max[0] = queue.peek()[0]; // 此时堆顶元素为当前的最大值
int cur = 1; // 定义最大值结果集填充位置(也是当前滑动窗口左边界位置)
// 继续遍历剩余数组元素
for (int i = k; i < len; i++) {
// 1.新元素入堆
queue.offer(new int[]{nums[i], i});
// 2.如果当前最大值的元素所在索引小于当前边界左侧（说明已经滑出了滑动窗口可以直接去除，即弹出元素）
while (queue.peek()[1] < cur) { // 当出现大于等于cur边界的索引值，说明该最大值在窗口内
queue.poll();
}
max[cur++] = queue.peek()[0]; // 此时栈顶元素就是对应当前滑动窗口的最大值
}
// 返回结果
return max;
}
}
复杂度分析
- 时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。在最坏情况下，数组 nums 中的元素单调递增，那么最终优先队列中包含了所有元素，没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O(logn)，因此总时间复杂度为 O(nlogn)
- 空间复杂度：O(n)，即为优先队列需要使用的空间（一般计算的是额外的使用空间，结果集存储空间另作讨论）
👻方法2：单调队列（todo 单调队列思路）
思路分析：使用一个队列存储
复杂度分析
时间复杂度：
空间复杂度：
3.解题误区
❌动态规划方向思考
一开始看到题意，思考是否可以用动态规划的思路，构建dp[]存储以每个元素i为起点的滑动窗口的最大值。但是在分析状态转移方程的时候发现dp[i]和dp[i-1]的关系很难节点，首先数组可能会存在重复元素，因此无法界定窗口移动后这个上一个窗口的最大值会不会就被移出去了，导致状态方程存在多种情况
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
// 1.定义dp
int[] dp = new int[len - k]; // dp[i] 表示以i为起点的滑动窗口的最大值
// 2.初始化dp（计算第一个区间的Math）
for (int i = 0; i < k; i++) {
dp[0] = Math.max(dp[0], nums[i]);
}
// 3.构建dp（动态规划公式：dp[i]: 窗口移动移除了i-1，移入了i+k（不好判断：数组元素可能重复、没法界定移除的是不是最大的那个，还要额外判断））
for (int i = 1; i < len - k; i++) {
......
}
// 返回结果集
return dp;
}
🟡347-前K个高频元素
1.题目内容
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
1 <= nums.length <= 105k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
**进阶：**你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
2.题解思路
👻方法1：暴力法（计数+排序）
复杂度分析
时间复杂度：
空间复杂度：
👻方法2：计数+堆
大顶堆
/**
* 347 前K个高频元素
*/
public class Solution1 {
/**
* 暴力法：统计每个元素出现的频率（次数），然后进行排序，返回前K的元素
*/
public int[] topKFrequent(int[] nums, int k) {
// 1.统计每个元素出现的频率（次数）
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
// 2.基于频率进行排序（或者借助堆来构建前K）
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
// 大顶堆存储的是数组元素，排序规则则需根据数组元素获取到频率进行比较
@Override
public int compare(Integer o1, Integer o2) {
return map.get(o2) - map.get(o1); // 根据元素对应的出现频次进行比较构建
}
});
Iterator<Integer> keySetIterator = map.keySet().iterator();
while (keySetIterator.hasNext()) {
queue.offer(keySetIterator.next());
}
// 3.遍历大顶堆K（K个元素）
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = queue.poll();
}
// 返回结果
return res;
}
}
复杂度分析
时间复杂度：O（n logK） 遍历数组（n为数组长度）、哈希表记录元素出现次数（O（1））、入大顶堆（O（logK））
空间复杂度：O（n）需借助哈希表存储元素 ，堆存储元素（堆的大小会小于等于N）
小顶堆
/**
* 347 前K个高频元素
*/
public class Solution2 {
/**
* 暴力法：统计每个元素出现的频率（次数），然后进行排序，返回前K的元素
*/
public int[] topKFrequent(int[] nums, int k) {
// 1.统计每个元素出现的频率（次数）
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
// 2.基于频率进行排序（或者借助堆来构建前K）,此处采用小顶堆实现
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
// 小顶堆存储的是数组元素，排序规则则需根据数组元素获取到频率进行比较
@Override
public int compare(Integer o1, Integer o2) {
return map.get(o1) - map.get(o2); // 根据元素对应的出现频次进行比较构建
}
});
/**
* 先录入K个元素(此处限定k>=map.size)
* 然后遍历剩余元素，判断当前遍历元素和堆顶元素的关系：如果大于堆顶则置换，慢慢将小值置换出来，最终遍历完成后小顶堆留存的就是最大的前K
*/
for (int key : map.keySet()) {
if (queue.size() < k) { // 当小顶堆个数不足K则依次添加
queue.offer(key);
} else {
if (map.get(queue.peek()) < map.get(key)) { // 当小顶堆个数大于等于K，则依次将小顶堆的频率最小的置换出来
// 置换
queue.poll();
queue.offer(key);
}
}
}
// 3.遍历小顶堆
int[] res = new int[k];
int cur = 0;
while (!queue.isEmpty()) {
res[cur++] = queue.poll();
}
// 返回结果
return res;
}
public static void main(String[] args) {
int[] nums = new int[]{1, 1, 1, 2, 2, 3};
Solution2 solution2 = new Solution2();
solution2.topKFrequent(nums, 2);
}
}
复杂度分析
时间复杂度：O（n logK） 遍历数组（n为数组长度）、哈希表记录元素出现次数（O（1））、入大顶堆（O（logK））
空间复杂度：O（n）需借助哈希表存储元素 ，堆存储元素（O（k），小顶堆空间占用）
/**
* 🟡 347 前K个高频元素 - https://leetcode.cn/problems/top-k-frequent-elements/description/
*/
public class Solution347_02 {
/**
* 思路分析：top k 问题（统计元素出现频率，构建堆进行处理（大顶堆 或 维护k个元素的小顶堆））
*/
public int[] topKFrequent(int[] nums, int k) {
// ① 统计元素出现频率(<val,cnt>=><元素值,出现次数>)
Map<Integer, Integer> map = new HashMap<>();
for (int x : nums) {
map.put(x, map.getOrDefault(x, 0) + 1);
}
// ② 构建小顶堆
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
// new int[]{val,cnt}
@Override
public int compare(int[] o1, int[] o2) {
return o2[1] == o1[1] ? o1[0] - o2[0] : o1[1] - o2[1]; // 优先按照出现频次排序，其次按照元素从小到大排序
}
});
// 维护K个元素的小顶堆
Set<Integer> keySet = map.keySet();
int cur = 0;
for (int val : keySet) {
if (cur < k) {
// 初始化维护K个元素
pq.offer(new int[]{val, map.get(val)});
cur++;
} else {
// 遍历剩余元素（将其与堆顶元素进行比较，依次将堆中的最小值置换出来）
int curTopVal = pq.peek()[0];
int curTopCnt = pq.peek()[1];
if (curTopCnt < map.get(val)) {
// 置换较小出现频次的元素
pq.poll();
pq.offer(new int[]{val, map.get(val)});
cur++;
}
}
}
// ③ 当前堆中剩余的即为前K大出现频次元素
int[] res = new int[k];
int p = 0;
while (!pq.isEmpty()) {
res[p++] = pq.poll()[0];
}
// 返回结果集合
return res;
}
public static void main(String[] args) {
int[] nums = new int[]{1, 1, 1, 2, 2, 3};
Solution347_02 solution = new Solution347_02();
solution.topKFrequent(nums, 2);
}
}
Powered by Waline v3.1.3