Solution 2: Min Stack

问题描述

定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。

实现栈的push(), pop()及getMin()函数,要求函数的时间复杂度为O(1).

解决思路

使用两个栈,一个为普通栈,实现push和pop函数;另一个记录所有入栈元素的非递增序列;

如下图所示:

程序

public class MinStack {
	private Stack<Integer> normal;
	private Stack<Integer> min;

	public MinStack() {
		normal = new Stack<Integer>();
		min = new Stack<Integer>();
	}

	public void push(int elem) {
		normal.push(elem);
		if (min.isEmpty() || min.peek() >= elem) {
			min.push(elem);
		}
	}

	public int pop() throws Exception {
		if (normal.isEmpty()) {
			throw new Exception("Error: The Stack is Empty!");
		}
		int res = normal.pop();
		if (min.peek() == res) {
			min.pop();
		}
		return res;
	}

	public int getMin() throws Exception {
		if (min.isEmpty()) {
			throw new Exception("Error: The Stack is Empty!");
		}
		return min.peek();
	}
}
时间: 06-27

Solution 2: Min Stack的相关文章

2016.6.1——Min Stack

Min Stack 本题收获: 1.可以利用两个栈操作. 2.栈的基本操作. 题目: 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

LeetCode: Min Stack 解题报告

Min Stack My Submissions Question Solution 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

[LeetCode] Min Stack Min Stack

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

用stack实现min stack

遇到个好玩的问题,就是用一个stack实现min stack,什么意思呢,就是我实现stack,但是能以O(1)的时间复杂度和空间复杂度去找到我stack里面的最小值. 常规的方法是:用一个变量存放当前最小值,但是会出现这种情况,就是当我的stack pop掉的值刚好是最小值时候,后面就没法知道当前的最小值了. 怎么办呢?可以考虑在push阶段做个改变,就是在我每次往stack里面push数据的时候,跟当前的最小值比较,如果比当前最小值还小的话,那么将当前最小值入栈,再把最小值修改为这个值.在p

【leetcode】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 e

Min Stack 解答

Question 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

Min Stack leetcode

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 e

Min Stack (10)

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 e

[leedcode 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 e