155. 最小栈
目录
题目链接：
题目：
解题思路：
代码：
总结：
题目链接：
155. 最小栈 - 力扣（LeetCode）
题目：
设计一个支持 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
解题思路：
使用 辅助栈即可,辅助栈只存储最小值,然后 当出栈时候顺带也判断一下是否是辅助栈即可
代码：
class MinStack {Stack<Integer> st,min_st;public MinStack() {st=new Stack<>();min_st=new Stack<>();}public void push(int val) {st.push(val);if(min_st.isEmpty()|| val<=min_st.peek()){min_st.push(val);}}public void pop() {if(st.pop().equals(min_st.peek())){min_st.pop();}}public int top() {return st.peek();}public int getMin() {return min_st.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();*/
详解字符串相乘算法：不依赖内置函数实现大数乘法
在日常开发中，我们可能会遇到处理超大整数相乘的场景，当数字超过编程语言原生整数类型的表示范围时，直接转换为整数进行计算会导致溢出。本文将详细解析一个高效的字符串相乘算法，该算法不依赖任何内置大数处理库，完全通过模拟手工乘法的方式实现两个大整数的相乘运算。
问题分析
题目要求我们实现两个以字符串形式表示的非负整数的相乘，并且返回它们的乘积的字符串形式。关键约束是：
不能使用任何内置的 BigInteger 库
不能直接将输入转换为整数（因为输入可能非常大，超过整数类型的表示范围）
输入字符串长度最长可达 200 位，这意味着直接转换为整数类型是完全不可行的
例如，当输入为 "123" 和 "456" 时，我们需要返回 "56088"，这正是这两个数相乘的结果。
算法思路
这个问题的解决方案灵感来源于我们小学时学习的手工乘法计算方法：
将两个数按位相乘
处理进位
将所有中间结果相加
具体到算法实现上，我们可以使用一个数组来存储每一位的计算结果，数组的长度为两个输入字符串长度之和（因为两个分别为 m 位和 n 位的数相乘，结果最多为 m+n 位）。
代码逐行解析
让我们来详细解析这个字符串相乘的实现代码：
字符串相乘算法实现
V1
创建时间：14:18
1. 特殊情况处理
java
运行
if(num1.equals("0")||num2.equals("0")){
return "0";
}
这段代码处理了乘法运算中的一个特殊情况：如果其中一个乘数是 0，那么乘积一定是 0。这是一个重要的优化，能避免不必要的计算。
2. 结果数组初始化
java
运行
int[] arr = new int[num1.length() + num2.length()];
我们创建了一个整数数组来存储乘法的中间结果和最终结果。数组的长度设置为两个输入字符串的长度之和，这是因为：
一个 m 位的数和一个 n 位的数相乘，结果最多有 m+n 位
例如：999（3 位）× 99（2 位）= 98901（5 位）
3. 嵌套循环实现逐位相乘
java
运行
for(int i = num2.length() - 1; i >= 0; i--){
int n2 = num2.charAt(i) - '0';
for(int j = num1.length() - 1; j >= 0; j--){
int n1 = num1.charAt(j) - '0';
// ... 计算逻辑
}
}
这里使用了嵌套循环来模拟手工乘法的过程：
外层循环遍历第二个数（num2）的每一位，从个位开始（从后往前）
内层循环遍历第一个数（num1）的每一位，同样从个位开始
num2.charAt(i) - '0' 是将字符型数字转换为对应的整数，例如 '5' - '0' 的结果是 5
4. 核心计算逻辑
java
运行
int sum = arr[i + j + 1] + n1 * n2;
arr[i + j + 1] = sum % 10;
arr[i + j] += sum / 10;
这部分是算法的核心，实现了每一位的乘法和进位处理：
计算当前乘积与进位之和：sum = arr[i + j + 1] + n1 * n2
n1 * n2 是当前两位数字的乘积
arr[i + j + 1] 是之前计算中存储在当前位置的进位值
更新当前位的值：arr[i + j + 1] = sum % 10
取 sum 除以 10 的余数，得到当前位的结果
例如，如果 sum 是 28，那么当前位应该是 8
处理进位：arr[i + j] += sum / 10
取 sum 除以 10 的商，得到需要进位的值
例如，如果 sum 是 28，那么进位值是 2
将进位值累加到更高位（i + j 的位置）
为什么使用i + j + 1和i + j作为索引？
这是由乘法的位对齐规则决定的
当 num2 的第 i 位（从 0 开始，从右向左）与 num1 的第 j 位相乘时，结果的最低位应该放在 i + j + 1 的位置
进位则放在更高一位的 i + j 位置
5. 结果转换为字符串
java
运行
StringBuilder sc = new StringBuilder();
for(int i = 0; i < arr.length; i++){
if(i == 0 && arr[i] == 0) continue;
sc.append(arr[i]);
}
return sc.toString();
设计常数时间获取最小值的栈：MinStack 实现详解
在栈的基本操作中，push、pop 和 top 都可以在常数时间内完成，但获取栈中的最小元素通常需要遍历整个栈，时间复杂度为 O (n)。本文将详细解析一个优雅的解决方案，通过辅助栈的设计，实现所有操作（包括获取最小值）在常数时间内完成。
问题分析
题目要求我们设计一个支持以下操作的栈：
push(val)：将元素 val 推入堆栈
pop()：删除堆栈顶部的元素
top()：获取堆栈顶部的元素
getMin()：检索堆栈中的最小元素
关键约束是 getMin () 操作必须在常数时间内完成，这意味着我们不能在每次调用 getMin () 时遍历整个栈来寻找最小值。
例如，当执行以下操作序列：
plaintext
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // 返回 -3
minStack.pop();
minStack.top(); // 返回 0
minStack.getMin(); // 返回 -2
我们需要确保每次操作都能高效执行，特别是 getMin () 必须在 O (1) 时间内返回正确结果。
解决方案：双栈设计
解决这个问题的经典方案是使用双栈结构：
一个主栈（st）：用于存储所有元素，支持正常的栈操作
一个辅助栈（min_st）：专门用于跟踪最小值，栈顶元素始终是当前主栈中的最小元素
这种设计的核心思想是：在每次推入元素时，同步维护辅助栈，确保辅助辅助栈的栈顶元素始终是当前主栈中的最小值。
代码实现
下面是完整的 MinStack 实现代码：
常数时间获取最小值的栈实现
V1
创建时间：14:36
代码逐行解析
1. 类成员变量
java
运行
Stack<Integer> st;
Stack<Integer> min_st;
我们声明了两个栈：
st：主栈，用于存储所有元素，实现基本的栈操作
min_st：辅助栈，专门用于跟踪最小值，其栈顶元素始终是当前主栈中的最小元素
2. 构造方法
java
运行
public MinStack() {
st = new Stack<>();
min_st = new Stack<>();
}
构造方法初始化了两个栈对象，准备接收元素。
3. push 方法
java
运行
public void push(int val) {
st.push(val);
if(min_st.isEmpty() || val <= min_st.peek()){
min_st.push(val);
}
}
push 方法是整个实现的核心，它完成了两项关键操作：
将元素 val 推入主栈 st
维护辅助栈 min_st：
如果辅助栈为空（即这是第一个推入的元素），直接将 val 推入辅助栈
如果 val 小于或等于辅助栈的栈顶元素，则将 val 推入辅助栈
这里使用 val <= min_st.peek() 而不是 val < min_st.peek() 是为了处理重复元素的情况。例如，当主栈中有多个相同的最小值时，辅助栈也需要相应数量的该值，以确保在弹出操作后仍能正确跟踪最小值。
4. pop 方法
java
运行
public void pop() {
if(st.pop().equals(min_st.peek())){
min_st.pop();
}
}
pop 方法用于删除栈顶元素，同样需要维护辅助栈的一致性：
从主栈 st 中弹出栈顶元素
检查弹出的元素是否等于辅助栈 min_st 的栈顶元素：
如果相等，说明弹出的是当前最小值，因此也需要从辅助栈中弹出栈顶元素
如果不相等，辅助栈保持不变
注意这里使用 equals() 而不是 == 来比较整数，这是因为 Stack 中存储的是 Integer 对象，对于较大的整数，== 可能会导致错误的比较结果。
5. top 方法
java
运行
public int top() {
return st.peek();
}
top 方法简单地返回主栈 st 的栈顶元素，这是标准的栈操作。
6. getMin 方法
java
运行
public int getMin() {
return min_st.peek();
}
getMin 方法是这个设计的亮点，它直接返回辅助栈 min_st 的栈顶元素，这就是当前主栈中的最小值。由于栈的 peek 操作是 O (1) 时间复杂度，因此 getMin 方法也实现了常数时间的查询。
算法执行过程演示
让我们通过示例操作序列来演示算法的执行过程：
初始化：MinStack minStack = new MinStack();
st = []，min_st = []
push(-2)：
st 变为 [-2]
min_st 为空，所以也推入 -2，min_st 变为 [-2]
push(0)：
st 变为 [-2, 0]
0 > min_st 栈顶 (-2)，所以 min_st 保持不变，仍为 [-2]
push(-3)：
st 变为 [-2, 0, -3]
-3 <min_st 栈顶 (-2)，所以推入 -3，min_st 变为 [-2, -3]
getMin()：
返回 min_st 栈顶元素 -3
pop()：
从 st 弹出 -3
弹出的元素 (-3) 等于 min_st 栈顶元素，所以也从 min_st 弹出 -3
操作后：st = [-2, 0]，min_st = [-2]
top()：
返回 st 栈顶元素 0
getMin()：
返回 min_st 栈顶元素 -2
这个执行过程完全符合示例的预期输出，验证了算法的正确性。
复杂度分析
时间复杂度
push(val)：O (1)，两个栈的 push 操作都是常数时间
pop()：O (1)，两个栈的 pop 操作都是常数时间
top()：O (1)，栈的 peek 操作是常数时间
getMin()：O (1)，直接返回辅助栈的栈顶元素
所有操作都实现了常数时间复杂度，满足题目的要求。
空间复杂度
最坏情况下为 O (n)，其中 n 是栈中元素的数量
当元素按严格递减顺序推入栈时，辅助栈将存储所有元素，与主栈大小相同
算法优势与局限性
优势
高效性：所有操作都在常数时间内完成
简洁性：实现简单直观，易于理解和维护
可靠性：通过辅助栈与主栈的同步维护，确保了最小值的准确性
局限性
空间开销：需要额外的辅助栈存储最小值信息，在最坏情况下空间复杂度为 O (n)
只支持整数：当前实现只支持整数类型，如需支持其他类型需要泛型化处理
可能的优化与变体
虽然当前实现已经非常高效，但我们可以考虑一些变体实现：
1. 单栈优化方案
可以使用一个栈同时存储元素和当前最小值，每次推入一个数组或对象，包含当前值和当前最小值。这种方案空间复杂度相同，但减少了一个栈对象的使用。
java
运行
class MinStack {
Stack<int[]> stack;
public MinStack() {
stack = new Stack<>();
}
public void push(int val) {
if (stack.isEmpty()) {
stack.push(new int[]{val, val});
} else {
int currentMin = stack.peek()[1];
stack.push(new int[]{val, Math.min(val, currentMin)});
}
}
public void pop() {
stack.pop();
}
public int top() {
return stack.peek()[0];
}
public int getMin() {
return stack.peek()[1];
}
}
2. 差值存储方案
另一种优化是只使用一个栈，存储当前值与当前最小值的差值。这种方案可以节省一定的空间，但实现稍复杂，且需要处理整数溢出的问题。
实际应用场景
这种能够在常数时间获取最小值的栈在实际开发中有很多应用场景：
表达式求值：在计算表达式时，需要跟踪当前的最小值或最大值
算法优化：许多算法（如单调栈相关算法）可以利用这种数据结构优化性能
编辑器撤销功能：在实现撤销功能时，需要跟踪不同状态下的某些属性最小值
金融数据分析：在处理时间序列数据时，需要快速获取某段时间内的最小值
总结
本文详细解析了一种使用双栈实现的 MinStack 数据结构，它能够在常数时间内支持 push、pop、top 和 getMin 操作。这种设计的核心思想是使用一个辅助栈同步跟踪主栈中的最小值，确保 getMin 操作的高效性。
算法的时间复杂度为 O (1)（所有操作），空间复杂度为 O (n)（最坏情况）。这种实现方式既简洁又高效，是解决此类问题的经典方案。
理解并掌握这种设计思想，不仅能帮助我们解决类似的编程问题，还能培养我们在数据结构设计中权衡时间和空间复杂度的思维能力。在实际开发中，当需要频繁获取集合中的极值时，这种辅助结构的设计思路值得借鉴。
总结：
本文介绍了两道经典算法题的解法。第一题通过双栈设计实现最小栈（MinStack），主栈存储元素，辅助栈同步维护当前最小值，确保push、pop、top和getMin操作均在O(1)时间内完成。第二题采用手工乘法模拟实现大数相乘的字符串算法，通过数组存储中间结果并按位处理乘积和进位，最终将结果转为字符串。两题均展示了如何通过辅助数据结构优化算法性能，分别解决了常数时间获取极值和避免数值溢出的问题，体现了算法设计中时间与空间复杂度的权衡思维。