力扣155.最小栈
原题，题目描述：
这题力扣分类是中等，不过其实也不算难吧只能说，但是要是刚开始刷题可能会一时半会想不到。
思路
这题主要还是难在我们需要在常数时间复杂度内返回最小值，我们只添加元素还好，就可以直接记录当前最小值即可，但是一旦删除元素，我们就不能保证是否是最小值被删除，以及如何得到新的最小值。这个问题我们可以通过一个辅助的栈来解决，这个辅助栈只存储到某一个位置（包括这个位置）往前的最小值，这建立在栈只能通过一个入口，一个出口的前提下，如果是队列甚至双端队列，那情况会更加复杂，但是我们这道题不用考虑那么多。
代码
class MinStack {
private int[] arr;
private int top;
private int[] min;
public MinStack() {
arr = new int[1];
min = new int[1];
top = -1;
}
public void push(int val) {
++top;
if (top >= arr.length) {
int[] temp = new int[2 * arr.length];
System.arraycopy(arr, 0, temp, 0, arr.length);
arr = temp;
temp = new int[2 * arr.length];
System.arraycopy(min, 0, temp, 0, min.length);
min = temp;
}
if (top == 0 || val < min[top - 1]) {
min[top] = val;
} else {
min[top] = min[top - 1];
}
arr[top] = val;
}
public void pop() {
--top;
}
public int top() {
return arr[top];
}
public int getMin() {
return min[top];
}
}
/**
* 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();
*/
我们是原原本本按照思路写的代码，功能也符合题目要求。提交打败百分百。
变种
这道题其实还有变种，难度升级的版本。我们前面这个解法是借用了一个辅助栈来帮助存储最小值，现在要求只能使用一个栈。这里放一个解决方案。并且这是字节跳动面试原题，大家可以看看。