励志：🔔半身浸江，全身如林，所谓万丈深渊，下去也是前程万里。我启程了，你呢?
一、LIFO栈
1.逆序链表
题：剑指 Offer 06. 从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
限制：
0 <= 链表长度 <= 10000
解：
解题思路：辅助栈
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] reversePrint(ListNode head) {
Stack<Integer> stack = new Stack<>();
while(head != null) {
stack.push(head.val);
head = head.next;
}
int[] res = new int[stack.size()];
for(int i = 0; i < res.length; i ++) {
res[i] = stack.pop();
}
return res;
}
}- 时间复杂度：O（N），入栈、出栈使用O（N）时间
- 空间复杂度：O（N），辅助栈和数组使用额外的O（N）空间
解题思路：递归
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> arr = new ArrayList<>();
public int[] reversePrint(ListNode head) {
dfs(head);
return arr.stream().mapToInt(k -> k).toArray();
}
void dfs(ListNode node) {
if(node == null) return; // 递归出口
dfs(node.next);
arr.add(node.val);
}
}- 时间复杂度：O（N）
- 空间复杂度：O（N）
题：206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]示例 2：
输入：head = [1,2]
输出：[2,1]示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
解：
解题思路：三人行模板
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode pre = null;
ListNode cur = head;
while(cur != null) {
ListNode node = cur.next;
cur.next = pre;
pre = cur;
cur = node;
}
return pre;
}
}- 时间复杂度：O（N），遍历链表，N为链表长度
- 空间复杂度：O（1），指针消耗常数空间O（1）
解题思路：递归
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) return head;
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}- 时间复杂度：O（N）
- 空间复杂度：O（1）
2.括号匹配
题：20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true示例 2：
输入：s = "()[]{}"
输出：true示例 3：
输入：s = "(]"
输出：false示例 4：
输入：s = "([)]"
输出：false示例 5：
输入：s = "{[]}"
输出：true
提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成
解：
解题思路：辅助栈
AC代码：
class Solution {
public boolean isValid(String s) {
if((s.length() & 1) != 0) return false; // s长度为奇数
Map<Character, Character> map = new HashMap<>(){{
put(')', '(');
put('}', '{');
put(']', '[');
}};
Stack<Character> stack = new Stack<>();
for(Character ch : s.toCharArray()) {
if(map.containsKey(ch)) {
if(stack.isEmpty() || stack.peek() != map.get(ch)) {
return false;
}
stack.pop();
}else {
stack.push(ch);
}
}
return stack.isEmpty(); // 注意栈判空
}
}- 时间复杂度：O（N），N为字符串长度。
- 空间复杂度：O（N +C），N为栈长，C为字符集。
题：32. 最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"示例 3：
输入：s = ""
输出：0
提示：
0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'
解：
📖 解题思路：动态规划
- 最长 => 动态规划
- dp[i]表示以i结尾的最长有效括号
- 情况分类讨论：
AC代码：
class Solution {
public int longestValidParentheses(String s) {
int[] dp = new int[s.length()];
int maxVal = 0;
// dp[0] = 0;
for(int i = 1; i < dp.length; i ++) {
if(s.charAt(i) == ')') {
if(s.charAt(i - 1) == '(') {
dp[i] = 2; // ()
if(i - 2 >= 0) { // ()()
dp[i] = dp[i - 2] + 2;
}
}else if(dp[i - 1] > 0) {
if(i - dp[i - 1] - 1 >= 0 && s.charAt(i - dp[i - 1] - 1) == '(') { // (())
dp[i] = dp[i - 1] + 2;
if((i - dp[i - 1] - 2) >= 0) { // ()(())
dp[i] += dp[i - dp[i - 1] - 2];
}
}
}
}
maxVal = Math.max(maxVal, dp[i]);
}
return maxVal;
}
}- 时间复杂度：O（N），N为字符串长度，遍历整个字符串一次，求出dp数组
- 空间复杂度：O（N），N为数组dp的大小
解题思路：栈
AC代码：
class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<>(); // 栈存储字符串下标
int maxVal = 0;
stack.push(-1); // 防止栈判空
for(int i = 0; i < s.length(); i ++) {
if(s.charAt(i) == '(') {
stack.push(i);
}else {
stack.pop();
if(stack.isEmpty()) {
stack.push(i);
}else {
maxVal = Math.max(maxVal, i - stack.peek());
}
}
}
return maxVal;
}
}- 时间复杂度：O（N）
- 空间复杂度：O（N）
3.回文链表
题：剑指 Offer II 027. 回文链表
给定一个链表的 头节点 head ，请判断其是否为回文链表。
如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。
示例 1：
输入: head = [1,2,3,3,2,1]
输出: true示例 2：
输入: head = [1,2]
输出: false
提示：
链表 L 的长度范围为 [1, 105]
0 <= node.val <= 9
进阶：能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解：
解题思路：
- 找中点
- 反转后半
- 比对
- 还原（可有可无）
AC代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null || head.next == null) return true;
// 1.找中点
ListNode mid = getMid(head);
// 2.反装后半 123 2 | 1234 2
ListNode temp = mid.next;
mid.next = null;
ListNode B = reverseList(temp);
// 3.比对
boolean flag = compareList(head, B);
// 4.还原
mid.next = reverseList(B);
return flag;
}
// 链表取中点
ListNode getMid(ListNode head) {
ListNode p = head, q = head;
while(q.next != null && q.next.next != null) {
p = p.next;
q = q.next.next;
}
return p;
}
// 链表反装
ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
// 链表比较
boolean compareList(ListNode A, ListNode B) {
// A可能比B长
while(B != null) {
if(A.val != B.val) return false;
A = A.next;
B = B.next;
}
return true;
}
}- 时间复杂度：O（N），N为链表长度
- 空间复杂度：O（1），指针消耗常数空间
题：234. 回文链表
题：面试题 02.06. 回文链表
4.表达式求值
题：682. 棒球比赛
你现在是一场采用特殊赛制棒球比赛的记录员。这场比赛由若干回合组成，过去几回合的得分可能会影响以后几回合的得分。
比赛开始时，记录是空白的。你会得到一个记录操作的字符串列表 ops，其中 ops[i] 是你需要记录的第 i 项操作，ops 遵循下述规则：
- 整数 x - 表示本回合新获得分数 x
- "+" - 表示本回合新获得的得分是前两次得分的总和。题目数据保证记录此操作时前面总是存在两个有效的分数。
- "D" - 表示本回合新获得的得分是前一次得分的两倍。题目数据保证记录此操作时前面总是存在一个有效的分数。
- "C" - 表示前一次得分无效，将其从记录中移除。题目数据保证记录此操作时前面总是存在一个有效的分数。
请你返回记录中所有得分的总和。
示例 1：
输入：ops = ["5","2","C","D","+"]
输出：30
解释：
"5" - 记录加 5 ，记录现在是 [5]
"2" - 记录加 2 ，记录现在是 [5, 2]
"C" - 使前一次得分的记录无效并将其移除，记录现在是 [5].
"D" - 记录加 2 * 5 = 10 ，记录现在是 [5, 10].
"+" - 记录加 5 + 10 = 15 ，记录现在是 [5, 10, 15].
所有得分的总和 5 + 10 + 15 = 30示例 2：
输入：ops = ["5","-2","4","C","D","9","+","+"]
输出：27
解释：
"5" - 记录加 5 ，记录现在是 [5]
"-2" - 记录加 -2 ，记录现在是 [5, -2]
"4" - 记录加 4 ，记录现在是 [5, -2, 4]
"C" - 使前一次得分的记录无效并将其移除，记录现在是 [5, -2]
"D" - 记录加 2 * -2 = -4 ，记录现在是 [5, -2, -4]
"9" - 记录加 9 ，记录现在是 [5, -2, -4, 9]
"+" - 记录加 -4 + 9 = 5 ，记录现在是 [5, -2, -4, 9, 5]
"+" - 记录加 9 + 5 = 14 ，记录现在是 [5, -2, -4, 9, 5, 14]
所有得分的总和 5 + -2 + -4 + 9 + 5 + 14 = 27示例 3：
输入：ops = ["1"]
输出：1
提示：
- 1 <= ops.length <= 1000
- ops[i] 为 "C"、"D"、"+"，或者一个表示整数的字符串。整数范围是 [-3 104, 3 104]
- 对于 "+" 操作，题目数据保证记录此操作时前面总是存在两个有效的分数
- 对于 "C" 和 "D" 操作，题目数据保证记录此操作时前面总是存在一个有效的分数
解：
解题思路：栈
AC代码：
class Solution {
public int calPoints(String[] ops) {
Stack<Integer> stack = new Stack<>();
for(String op : ops) {
if(op.equals("+")) {
// 需要得到栈前两个元素，必须保存弹出栈元素
int a = stack.pop();
int b = a + stack.peek();
stack.push(a);
stack.push(b);
}else if(op.equals("C")) {
stack.pop();
}else if(op.equals("D")) {
int a = stack.peek();
stack.push(a * 2);
}else {
stack.push(Integer.valueOf(op));
}
}
int ans = 0;
for(int score : stack) ans += score;
return ans;
}
}- 时间复杂度：O（N），N是字符串ops的长度。
- 空间复杂度：O（N），用于存储stack的空间。
5.双栈判等
### 题：844. 比较含退格的字符串
给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
如果相等，返回 true ；否则，返回 false 。
注意：如果对空文本输入退格字符，文本继续为空。
示例 1：
输入：s = "ab#c", t = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。示例 2：
输入：s = "ab##", t = "c#d#"
输出：true
解释：s 和 t 都会变成 “”。示例 3：
输入：s = "a##c", t = "#a#c"
输出：true
解释：s 和 t 都会变成 “c”。示例 4：
输入：s = "a#c", t = "b"
输出：false
解释：s 会变成 “c”，但 t 仍然是 “b”。 提示：
- 1 <= s.length, t.length <= 200
s 和 t 只含有小写字母以及字符 '#'
解：
解题思路：
栈AC代码：
class Solution {
public boolean backspaceCompare(String s, String t) {
if(s == null || t == null) return false;
return buildStack(s.toCharArray()).equals(buildStack(t.toCharArray()));
}
public Stack<Character> buildStack(char[] chars) {
Stack<Character> stack = new Stack<>();
for(char ch : chars) {
if(ch == '#') {
if(!stack.isEmpty()) {
stack.pop();
}
}else {
stack.push(ch);
}
}
return stack;
}}
- 时间复杂度：O（N）
- 空间复杂度：O（N）
解题思路：`双指针`
AC代码：class Solution {
public boolean backspaceCompare(String s, String t) {
// 双指针法
int i = s.length() - 1, j = t.length() - 1;
int s_count = 0;
int t_count = 0;
while(i >= 0 || j >= 0) {
while(i >= 0) {
if(s.charAt(i) == '#') {
s_count ++;
i --;
}else if(s_count > 0){
s_count --;
i --;
}else {
break;
}
}
while(j >= 0) {
if(t.charAt(j) == '#') {
t_count ++;
j --;
}else if(t_count > 0) {
t_count --;
j --;
}else {
break;
}
}
if(i >= 0 && j >= 0) {
if(s.charAt(i) != t.charAt(j)) return false;
}else {
if(i >= 0 || j >= 0) return false;
}
i --;
j --;
}
return true;
}}
- 时间复杂度：O（N）
- 空间复杂度：O（1）
# 二、单调栈
## 1.最小栈
### 题：155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) —— 将元素 x 推入栈中。
- pop() —— 删除栈顶的元素。
- top() —— 获取栈顶元素。
- getMin() —— 检索栈中的最小元素。
示例:
输入：
["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.
提示：
pop、top 和 getMin 操作总是在 非空栈 上调用。
### 解：
解题思路：`递减栈`
AC代码：class MinStack {
Stack<Integer> stack;
Stack<Integer> min_stack;
public MinStack() {
stack = new Stack<>();
min_stack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if(min_stack.isEmpty() || val <= min_stack.peek()) {
min_stack.push(val);
}
}
public void pop() {
// 声明成 int 类型，完成自动拆箱，因此下面的比较可以使用 "==" 运算符
int x = min_stack.peek();
if(stack.pop() == x) {
min_stack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min_stack.peek();
}}
/**
- 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();
*/
另解：先将Integer自动拆箱为int，再比较class MinStack {
Stack<Integer> stack;
Stack<Integer> min_stack;
public MinStack() {
stack = new Stack<>();
min_stack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if(min_stack.isEmpty() || val <= min_stack.peek()) {
min_stack.push(val);
}
}
public void pop() {
// 或者直接用equals判等
if(stack.pop().equals(min_stack.peek())) {
min_stack.pop();
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min_stack.peek();
}}
/**
- 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();
*/
- 时间复杂度：O（1）
- 空间复杂度：O（N） 两个栈的大小
### 题：面试题 03.02. 栈的最小值
### 题：剑指 Offer 30. 包含min函数的栈
## 2.栈模拟队列
### 题：232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。
**进阶：**
- 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。
示例：
输入：
["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
提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）
### 解：
解题思路：`双栈模拟`
AC代码：class MyQueue {
Stack<Integer> in;
Stack<Integer> out;
public MyQueue() {
in = new Stack<>();
out = new Stack<>();
}
public void push(int x) {
in.push(x);
}
public int pop() {
if(out.isEmpty()) {
while(!in.isEmpty()) out.push(in.pop());
}
return out.pop();
}
public int peek() {
if(out.isEmpty()) {
while(!in.isEmpty()) out.push(in.pop());
}
return out.peek();
}
public boolean empty() {
return in.isEmpty() && out.isEmpty(); // 注意这里的优雅写法
}}
/**
- 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();
- boolean param_4 = obj.empty();
*/
- 时间复杂度：O（1）
- 空间复杂度：O（N），两个栈in，out所耗空间
### 题：剑指 Offer 09. 用两个栈实现队列
### 题：面试题 03.04. 化栈为队
## 3.辅助栈
### 题：1352. 最后 K 个数的乘积
请你实现一个「数字乘积类」ProductOfNumbers，要求支持下述两种方法：
1.add(int num)
- 将数字 num 添加到当前数字列表的最后面。
2.getProduct(int k)
- 返回当前数字列表中，最后 k 个数字的乘积。
- 你可以假设当前列表中始终 至少 包含 k 个数字。
题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。
示例：
输入：
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]
输出：
[null,null,null,null,null,null,20,40,0,null,32]
解释：
ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3); // [3]
productOfNumbers.add(0); // [3,0]
productOfNumbers.add(2); // [3,0,2]
productOfNumbers.add(5); // [3,0,2,5]
productOfNumbers.add(4); // [3,0,2,5,4]
productOfNumbers.getProduct(2); // 返回 20 。最后 2 个数字的乘积是 5 * 4 = 20
productOfNumbers.getProduct(3); // 返回 40 。最后 3 个数字的乘积是 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // 返回 0 。最后 4 个数字的乘积是 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8); // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // 返回 32 。最后 2 个数字的乘积是 4 * 8 = 32
提示：
add 和 getProduct 两种操作加起来总共不会超过 40000 次。
0 <= num <= 100
1 <= k <= 40000
### 解：
解题思路：`前缀积`
AC代码：/**
- 前缀积
*/
class ProductOfNumbers {
List<Integer> preProduct; // 前面的数字乘积
int Vlen; // 列表有效长度
public ProductOfNumbers() {
preProduct = new ArrayList<>();
Vlen = 0;
}
public void add(int num) {
if(num == 0) {
preProduct.clear();
Vlen = 0;
}else {
if(preProduct.size() == 0) preProduct.add(num);
else preProduct.add(preProduct.get(Vlen - 1) * num); // 注意下标从0开始
Vlen ++;
}
}
public int getProduct(int k) {
if(Vlen < k) return 0;
else if(Vlen == k) return preProduct.get(Vlen - 1);
return preProduct.get(Vlen - 1) / preProduct.get(Vlen - 1 - k); // 12345,345,k=3,=>12345/12
}}
/**
- Your ProductOfNumbers object will be instantiated and called as such:
- ProductOfNumbers obj = new ProductOfNumbers();
- obj.add(num);
- int param_2 = obj.getProduct(k);
*/
- 时间复杂度：O（1）
- 空间复杂度：O（N），额外的一个辅助列表
## 4.最大矩形
### 题：84. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1:
输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10
示例 2：
输入： heights = [2,4]
输出： 4
提示：
- 1 <= heights.length <=105
- 0 <= heights[i] <= 104
### 解：
解题思路：`单调栈`
单调栈模板：
/**
- 单调栈模板
*/
while(!stack.isEmpty() && stack.peek() < or > target) {
stack.pop();}
stack.push(i);
AC代码：class Solution {
public int largestRectangleArea(int[] heights) {
int res = 0;
Stack<Integer> stack = new Stack<>();
int[] newHeights = new int[heights.length + 2];
newHeights[0] = 0;
newHeights[newHeights.length - 1] = 0;
for(int i = 1; i < newHeights.length - 1; i ++) {
newHeights[i] = heights[i - 1];
}
// 单增栈
for(int i = 0; i < newHeights.length; i ++) {
// 栈不为空
while(!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
int height = newHeights[stack.pop()];
int left = stack.peek();
int right = i;
res = Math.max(res, height * (right - left - 1));
}
stack.push(i);
}
return res;
}}
- 时间复杂度：O（N）
- 空间复杂度：O（N）,newHeights数组、stack栈额外占用N空间
