Min Stack -- LeetCode
LeetCode -- Stack min
2023-09-11 14:14:08 时间
原题链接: https://oj.leetcode.com/problems/min-stack/
这道题是关于栈的题目,实现一个栈的基本功能,外加一个获得最小元素的操作。
这道题在理清思路之后代码还是比較简单的。这里用ArrayList来实现栈,当然也能够用链表,只是对于时间复杂度要求比較高,所以重点是想出维护最小栈顶做法。属于比較考察站的性质的题目,是非常不错的面试题目,在面经中也常常出现。
这道题是关于栈的题目,实现一个栈的基本功能,外加一个获得最小元素的操作。
正常情况下top。pop和push操作都是常量时间的,而主要问题就在于这个getMin上面,假设遍历一遍去找最小值,那么getMin操作就是O(n)的,既然出出来了这道题就肯定不是这么简单的哈。比較easy想到就是要追溯这个最小值。在push的时候维护最小值,可是假设pop出最小值的时候该怎样处理呢,怎样获得第二小的值呢?假设要去寻找又不是常量时间了。
解决的方案是再维护一个栈,我们称为最小栈,假设遇到更小的值则插入最小栈。否则就不须要插入最小栈(注意这里正常栈是怎么都要插进去的)。
这里的正确性在于。假设后来得到的值是大于当前最小栈顶的值的,那么接下来pop都会先出去,而最小栈顶的值会一直在,而当pop到最小栈顶的值时,一起出去后接下来第二小的就在pop之后最小栈的顶端了。如此push时最多插入两个栈一个元素,是O(1)。top是取正常栈顶,自然是O(1)。而pop时也是最多抛出两个栈的栈顶元素,O(1)。最后getMin仅仅须要peek最小栈顶栈顶就可以。所以仍是O(1)。实现了全部操作的常量操作。空间复杂度是O(n),最小栈的大小。代码例如以下:
class MinStack { ArrayList<Integer> stack = new ArrayList<Integer>(); ArrayList<Integer> minStack = new ArrayList<Integer>(); public void push(int x) { stack.add(x); if(minStack.isEmpty() || minStack.get(minStack.size()-1)>=x) { minStack.add(x); } } public void pop() { if(stack.isEmpty()) { return; } int elem = stack.remove(stack.size()-1); if(!minStack.isEmpty() && elem == minStack.get(minStack.size()-1)) { minStack.remove(minStack.size()-1); } } public int top() { if(!stack.isEmpty()) return stack.get(stack.size()-1); return 0; } public int getMin() { if(!minStack.isEmpty()) return minStack.get(minStack.size()-1); return 0; } }
这道题在理清思路之后代码还是比較简单的。这里用ArrayList来实现栈,当然也能够用链表,只是对于时间复杂度要求比較高,所以重点是想出维护最小栈顶做法。属于比較考察站的性质的题目,是非常不错的面试题目,在面经中也常常出现。
相关文章
- Leetcode--easy系列3
- 有序表的应用:[Leetcode]406. 根据身高重建队列
- [LeetCode] Kth Smallest Element in a BST
- [LeetCode] Swap Nodes in Pairs
- LeetCode数据结构_C语言题解系列-数组
- 84、【栈与队列】leetcode ——1047. 删除字符串中的所有相邻重复项:栈+双指针解法(C++版本)
- 【leetcode】日积月累,每日一题--707. 设计链表(DayDayUp 15)
- 【leetcode】日积月累,每日一题--26. 删除有序数组中的重复项(DayDayUp 11)【EDG加油】
- 【LeetCode】42. Trapping Rain Water
- 【LeetCode】63. Unique Paths II
- LeetCode--N-Queens
- Insertion Sort List -- leetcode
- [Leetcode]-Remove Duplicates from Sorted Array
- [LeetCode] 1015. Smallest Integer Divisible by K 可以整除K的最小整数
- [LeetCode] 875. Koko Eating Bananas 科科吃香蕉
- [LeetCode] 239. Sliding Window Maximum 滑动窗口最大值
- [LeetCode] 119. Pascal's Triangle II 杨辉三角之二
- Leetcode——21. Merge Two Sorted Lists