LeetCode155——最小栈
我的LeetCode代码仓:https://github.com/617076674/LeetCode
原题链接:https://leetcode-cn.com/problems/min-stack/description/
题目描述:
知识点:栈
思路:用一个int型成员变量min记录当前栈中的最小值
push(x)的时间复杂度是O(1)。
pop()操作由于要更新最小值min,其时间复杂度是O(n),其中n为栈中的元素个数。
top()的时间复杂度是O(1)。
getMin()的时间复杂度是O(1)。
JAVA代码:
public class MinStack {
private LinkedList<Integer> stack;
List<Integer> array;
int min;
public MinStack() {
stack = new LinkedList<>();
array = new ArrayList<>();
min = Integer.MAX_VALUE;
}
public void push(int x) {
stack.push(x);
array.add(x);
min = Math.min(min, x);
}
public void pop() {
int num = stack.pop();
array.remove(array.size() - 1);
if(array.size() > 0) {
min = array.get(0);
for (int i = 0; i < array.size(); i++) {
if(min > array.get(i)) {
min = array.get(i);
}
}
}else {
min = Integer.MAX_VALUE;
}
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}
LeetCode解题报告: