Leetcode:155. Min Stack
分析
利用一个LinkedList 链表存储数据,类似于链stack, 还有数组stack 采用ArrayList存储
关于如何查找最小元素的情况
思路一
最原始的方法:每次遍历存储元素的情况 ,时间复杂度为O(n)
代码
package data_struture;
import java.util.LinkedList;
import java.util.List;
/**
* 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 List<Integer> store;
public MinStack(){
store = new LinkedList<>();
}
//压入stack
public void push(int x){
this.store.add(x);
}
//弹出stack顶部的元素,删除
public void pop(){
this.store.remove(store.size() - 1);
}
//返回stack顶部的元素情况,不删除
public int top(){
return this.store.get(store.size()-1);
}
public int getMin() {
//产生每次对
int min= Integer.MAX_VALUE;
for (Integer i : store) {
if (i < min) {
min = i;
}
}
return min;
}
public static void main(String[] args) {
MinStack test =new MinStack();
test.push(-2);
test.push(0);
test.push(-3);
System.out.println(test.getMin());
test.pop();
System.out.println(test.top());
System.out.println(test.store.size());
System.out.println(test.getMin());
}
}
思路二:two stack
使用一个min, 记录stack中的最小值,但是也带来了问题,如果最小元素出stack后如何找到下一个最小的元素?
所以还是没有解决该问题
不容易想到用两个栈来存储数据,一个用于正常的存储栈数据,,另一个用于存储前一个栈的最小值。
一个stack存储真正的元素,另一min_stack记录最小元素的情况
上述min_stack存储的也是真正的元素情况,
** 当加入一个元素时,有两种情况下要加入min_stack**
- 第一次加入 元素,此时min_stack.isEmpty()==true;
- 当min_stack.peek()>=x时
代码
class MinStack {
stack<int> s;
stack<int> trackMin;
public:
void push(int x) {
if(trackMin.empty() || x<=trackMin.top())
trackMin.push(x);
s.push(x);
}
void pop() {
if(s.empty()) return;
if(s.top()==trackMin.top())
trackMin.pop();
s.pop();
}
int top() {
return s.top();
}
int getMin() {
return trackMin.top();
}
};
终极思路
如何设计一个时间复杂度为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;
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 (stack.isEmpty()) {
min = x;
stack.push(x);
}
//x<min 所以需要进行加密
if (x < min) {
min = x;
stack.push(2 * x - min);
} else {
stack.push(x);
}
}
//弹出stack顶部的元素,删除
public void pop() {
if (stack.isEmpty()) {
System.out.println("Stack is empty");
return;
}
System.out.print("Top Most Element Removed: ");
int y = stack.peek();
//需要揭秘
if (y < min) {
System.out.println(min);
min = 2 * min - y;
} else {
System.out.println(y);
}
}
//返回stack顶部的元素情况,不删除
public int top() {
if (stack.isEmpty()) {
System.out.println("Stack is empty ");
return -1;
}
Integer y = stack.peek();
System.out.println("Top Most Element is: ");
if (y >= min) {
return y;
} else {
return min;
}
}
public int getMin() {
if (stack.isEmpty()) {
System.out.println("stack is empty");
return -1;
}
return min;
}
public static void main(String[] args) {
MinStack test =new MinStack();
test.push(-2);
test.push(0);
test.push(-3);
System.out.println(test.getMin());
test.pop();
System.out.println(test.top());
System.out.println(test.stack.size());
System.out.println(test.getMin());
}
}