Leetcode题目155.最小栈（简单）
题目描述：
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例: MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
思路解析：
这道题的思想很简单：“以空间换时间”，使用辅助栈是常见的做法。
思路分析：
在代码实现的时候有两种方式：
1、辅助栈和数据栈同步
特点：编码简单，不用考虑一些边界情况，就有一点不好：辅助栈可能会存一些“不必要”的元素。（因为getMin要获取最小的元素，则当待入栈元素大于辅助栈栈顶元素值时，会再次入栈当前辅助栈的栈顶元素，因为最小值没有变化）
2、辅助栈和数据栈不同步
特点：由“辅助栈和数据栈同步”的思想，我们知道，当数据栈进来的数越来越大的时候，我们要在辅助栈顶放置和当前辅助栈顶一样的元素，这样做有点“浪费”。基于这一点，我们做一些“优化”，但是在编码上就要注意一些边界条件。
（1）辅助栈为空的时候，必须放入新进来的数；
（2）新来的数小于或者等于辅助栈栈顶元素的时候，才放入，特别注意这里“等于”要考虑进去，因为出栈的时候，连续的、相等的并且是最小值的元素要同步出栈；
（3）出栈的时候，辅助栈的栈顶元素等于数据栈的栈顶元素，才出栈。
总结一下：出栈时，最小值出栈才同步；入栈时，最小值入栈才同步。
对比：个人觉得“同步栈”的方式更好一些，因为思路清楚，因为所有操作都同步进行，所以调试代码、定位问题也简单。“不同步栈”，虽然减少了一些空间，但是在“出栈”、“入栈”的时候还要做判断，也有性能上的消耗。
代码实现：
一、数据栈和辅助栈同步
class MinStack {
/** initialize your data structure here. */
// 数据栈
private Stack<Integer> data;
// 辅助栈
private Stack<Integer> helper;
//构造函数初始化两个栈
public MinStack() {
data = new Stack<>();
helper = new Stack<>();
}
public void push(int x) {
data.add(x);
if (helper.isEmpty() || helper.peek() >= x) {
helper.add(x);
} else {
//辅助栈会加入一些"多余的元素"
helper.add(helper.peek());
}
}
public void pop() {
//注意辅助栈和数据栈要同步出栈,因为数据栈和辅助栈是同步出入栈（虽然元素可能不一样，但栈内数量是一致的）
if (!data.isEmpty()) {
data.pop();
helper.pop();
}
}
public int top() {
if (!data.isEmpty()) {
return data.peek();
} else {
throw new RuntimeException("数据栈内没有数据了");
}
}
public int getMin() {
if (!helper.isEmpty()) {
return helper.peek();
} else {
throw new RuntimeException("栈中元素为空，此操作非法");
}
}
}
/**
* 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();
*/
二、数据栈和辅助栈不同步
class MinStack {
// 数据栈
private Stack<Integer> data;
// 辅助栈
private Stack<Integer> helper;
//构造函数初始化两个栈
public MinStack() {
data = new Stack<>();
helper = new Stack<>();
}
public void push(int x) {
//数据栈一定要入
data.add(x);
//只有当新元素为新的最小值时，才会入辅助栈
if (helper.isEmpty() || helper.peek() >= x) {
helper.add(x);
}
}
public void pop() {
//数据栈一定要出
if (!data.isEmpty()) {
//只有当辅助栈的栈顶元素和出栈元素相同时，辅助栈才出栈
int top = data.pop();
if (top == helper.peek()) {
helper.pop();
}
}
}
public int top() {
if (!data.isEmpty()) {
return data.peek();
} else {
throw new RuntimeException("数据栈内没有数据了");
}
}
public int getMin() {
if (!helper.isEmpty()) {
return helper.peek();
} else {
throw new RuntimeException("栈中元素为空，此操作非法");
}
}
}
/**
* 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();
*/
时间复杂度：O(1)，“出栈”、“入栈”、“查看栈顶元素”的操作不论数据规模多大，都只有有限个步骤，因此时间复杂度是：O(1)。
空间复杂度：O(N)，这里 N 是读出的数据的个数。
最新文章
- React.js入门必须知道的那些事
- Entity Framework 6, database-first with Oracle
- NOIP欢乐模拟赛 T3 解题报告
- Solr5.3.1整合IKAnalyzer
- 使用foreach碰到的问题
- 什么是LBS?地理位置服务
- Conversion between json and object
- mysql 5.6 设置慢查询
- 用于下载AD官网登录账号：User name: fuxin918@fuxin918.com Passeword: s6c0W1w8
- 解决author波浪线Spellchecker inspection helps locate typos and misspelling in your code, comments and literals, and fix them in one click
- 在Ubuntu14.04下安装 labelImg (标数据用)
- form表单转换为Json数据
- python新手---学习第一天
- CSS层叠和继承
- 一些关于IO流的问题
- 编码原则 之 Once and Only Once
- linux环境下安装使用selenium Chrome
- 谈谈逆向android里面的so
- LevelDB源码分析-Compact
- Cracking The Coding Interview 9.0