leetcode链接
包含min函数的stack
分析
利用一个LinkedList 链表存储数据,类似于链stack, 还有数组stack 采用ArrayList存储
关于如何查找最小元素的情况
思路一 双stack
- stack 保存正常的元素情况
- min_stack 记录最小元素的顺序,
上述min_stack存储的也是真正的元素情况,
== 当加入一个元素时,有两种情况下要加入min_stack==
- 第一次加入 元素,此时min_stack.isEmpty()==true;
- 当min_stack.peek()>=x时
代码
Java stack当中是没有top(), 具有peek()
class MinStack {
/** initialize your data structure here. */
Stack<Integer> stack,minStack;
//
public MinStack() {
stack =new Stack<>();
minStack =new Stack<>();
}
public void push(int x) {
// 如何使保持一样的情况也是要进入
if(stack.isEmpty() || x<=minStack.peek())
// 在这种情况下,只有minStack和stack 当中的数量是不一致的 ,如果当前要进入stack的元素要小于
minStack.push(x);
stack.push(x);
}
public void pop() {
if(stack.isEmpty()) return;
if(stack.peek().intValue()==minStack.peek().intValue())
minStack.pop();
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
/**
* Your MinStack object will be instantiated and called as such:
* MinStack obj = new MinStack();
* obj.push(x);
* obj.pop();
* int param_3 = obj.top();
* int param_4 = obj.getMin();
*/
时间复杂度方面的情况
双stack的主要思想是
思路二:two stack
使用一个min, 记录stack中的最小值,但是也带来了问题,如果最小元素出stack后如何找到下一个最小的元素?
所以还是没有解决该问题
不容易想到用两个栈来存储数据,一个用于正常的存储栈数据,,另一个用于存储前一个栈的最小值。
一个stack存储真正的元素,另一min_stack记录最小元素的情况
终极思路
如何设计一个时间复杂度为O(1),空间复杂度为O(1), 只使用一个stack的情况,减少使用一个stack 的情况,
stack 不是存储真实压入的数据,minfile 是存储真实的最小数据情况
回到原来的思路: 采用一个stack记录数据,minfile记录最小值情况
push
假设要插入的是x , minfile 是最小数据情况
- 如果stack为空,是第一次插入数据情况,则直接插入, stack.push(x), min = x;
- 如果stack 不为空,
- 判断 x 与min 的大小情况,
- 如果 x>=min 的话, 对最小值没有影响,直接插入即可,也不用更新min
- 如果 x<min 的话, stack.push(2 * x - min ), 然后让 min =x ; 比如最小值为3, 现在新=2,2小于 3, 所以插入 2* 2-3 =1, 更新min =2;
为何插入2*x-min
==为何要插入2*x-premin 然后 current_min=x ==
主要是为了pop()的stack的元素标志是否是弹出stack中最小的元素
如果stack.peek()小于min, 说明要出弹出的就是最小元素,执行pop()操作要解密update min
如果stack.peek()大于等于min, 说明要min 还是留在stack 里面,不用update min,直接pop()
pop
int y =stack.peek()
- 如果y 大于或者等于 premin, 说明min 还在stack 中, 所以直接stack.pop() 后即可
- 如果y 小于 min, 那么说明真在的y 是 min, 直接返回 min然后 更新 min , min = 2 * premin- y,
总结
如果stack.peek < min , 那么原来的数据其实就是min ,真正要压入的数据
说白了就是对数据进行一定程度对变换即可,加密和揭秘过程,如果是stack.peek()>min, 或者x>=min , 直接插入即可,
当x<min ,才需要正在当更新整个数据当过程
**x 代表入stack, y 代表出stack, 即使 stack.peek()
使用这个两个元素与min, 进行一定程度对比较即可
如果 x <min ,需要进行加密压入,同时更新min
如果 y<min, 需要进行解密弹出, 同时更新min
**
package data_struture;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
/**
* 155. Min Stack
* Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
*
* push(x) -- Push element x onto stack.
* pop() -- Removes the element on top of the stack.
* top() -- Get the top element.
* getMin() -- Retrieve the minimum element in the stack. 要求使用
*/
public class MinStack {
//构造函数情况
private int min;
private Stack<Integer> stack;
public MinStack() {
stack = new Stack<>();
}
//压入stack
public void push(int x) {
//第一次处理整个元素当情况
if