背景
题目英文
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.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> Returns -3.
minStack.pop();
minStack.top(); --> Returns 0.
minStack.getMin(); --> Returns -2.
题目中文
设计一个支持 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.
算法实现
利用单链表的方式
public class MinStack
{
/** initialize your data structure here. */
private readonly IList<int> _lst;
public MinStack()
{
_lst = new List<int>();
}
public void Push(int x)
{
_lst.Add(x);
}
public void Pop()
{
_lst.RemoveAt(_lst.Count - 1);
}
public int Top()
{
return _lst[_lst.Count - 1];
}
public int GetMin()
{
return _lst.Min();
}
}
/**
* 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();
*/
利用辅助栈的方式
public class MinStack
{
/** initialize your data structure here. */
private readonly Stack<int> _stack;
private readonly Stack<int> _stackMin;
public MinStack()
{
_stack = new Stack<int>();
_stackMin = new Stack<int>();
}
public void Push(int x)
{
_stack.Push(x);
if (_stackMin.Count == 0 || _stackMin.Peek() >= x)
{
_stackMin.Push(x);
}
}
public void Pop()
{
int x = _stack.Pop();
if (_stackMin.Peek() == x)
{
_stackMin.Pop();
}
}
public int Top()
{
return _stack.Peek();
}
public int GetMin()
{
return _stackMin.Peek();
}
}
/**
* 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();
*/
实验结果
利用单链表的方式
- 状态：通过
- 18 / 18 个通过测试用例
- 执行用时: 776 ms, 在所有 C# 提交中击败了 22.32% 的用户
- 内存消耗: 33.8 MB, 在所有 C# 提交中击败了10.60% 的用户
利用辅助栈的方式
- 状态：通过
- 18 / 18 个通过测试用例
- 执行用时: 192 ms, 在所有 C# 提交中击败了 96.43% 的用户
- 内存消耗: 33.5 MB, 在所有 C# 提交中击败了 13.63% 的用户
相关图文
1. “数组”类算法
- LeetCode实战：三数之和
- LeetCode实战：最接近的三数之和
- LeetCode实战：求众数
- LeetCode实战：缺失的第一个正数
- LeetCode实战：快乐数
- LeetCode实战：寻找两个有序数组的中位数
- LeetCode实战：盛最多水的容器
- LeetCode实战：删除排序数组中的重复项
- LeetCode实战：搜索旋转排序数组
- LeetCode实战：螺旋矩阵
- LeetCode实战：螺旋矩阵 II
2. “链表”类算法
3. “栈”类算法
4. “队列”类算法
5. “递归”类算法
6. “字符串”类算法
7. “树”类算法
8. “哈希”类算法
9. “排序”类算法
10. “搜索”类算法
11. “动态规划”类算法
12. “回溯”类算法
13. “数值分析”类算法
转载：https://blog.csdn.net/LSGO_MYP/article/details/100976203
查看评论