Leetcode: Min Stack
LeetCode Stack min
2023-09-11 14:14:08 时间
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.
这是一道关于栈的题目,整体来说比较简单。我最开始想的时候想的太简单,以为使用一个栈st, 再维护一个最小值变量就好了。突然发现pop()操作之后需要更新这个最小值,那就需要知道第二小的值,这个第二小的值怎么找呢?于是乎我想到了使用另外一个栈minst专门来存储最小值。push()操作的时候每当x小于或等于(注意不是小于,之所以小于等于是为了元素重复的情况)minst的栈顶元素,minst也push x入栈。pop()操作时,如果pop出来的元素等于minst栈顶元素,那么minst栈也出栈。
这道题思路很简单,到时语法卡了我一会儿,老是过不了,一段时间不练手生啊。我的语法问题又出在==跟equals()上面。我栈的定义是Stack<Integer>。Integer是一个object。那么判断两个栈栈顶元素相等就不能写成 st.peek() == minst.peek(),这是地址相等,equals才是值相等。要改的话要么就改用equals,要么定义一个int elem = st.pop(); 再判断if (elem == minst.peek()), 这里是一个int 变量跟Integer对象相比,而不是两个Integer对象相比,==在这里就是表示值相等。
1 class MinStack { 2 Stack<Integer> st; 3 Stack<Integer> minst; 4 5 public MinStack() { 6 this.st = new Stack<Integer>(); 7 this.minst = new Stack<Integer>(); 8 } 9 10 public void push(int x) { 11 st.push(x); 12 if (minst.empty() || minst.peek()>=x) { 13 minst.push(x); 14 } 15 } 16 17 public void pop() { 18 if (st.isEmpty()) { 19 return; 20 } 21 if (st.peek().equals(minst.peek())) { 22 minst.pop(); 23 } 24 st.pop(); 25 } 26 27 public int top() { 28 if (!st.isEmpty()) { 29 return st.peek(); 30 } 31 return Integer.MAX_VALUE; 32 } 33 34 public int getMin() { 35 if (!minst.isEmpty()) { 36 return minst.peek(); 37 } 38 return Integer.MAX_VALUE; 39 } 40 }
(Adopted approach) use just one stack:
Push twice when min value changes.
Pop twice as well
1 class MinStack { 2 int min = Integer.MAX_VALUE; 3 Stack<Integer> stack = new Stack<Integer>(); 4 public void push(int x) { 5 // only push the old minimum value when the current 6 // minimum value changes after pushing the new value x 7 if(x <= min){ 8 stack.push(min); 9 min=x; 10 } 11 stack.push(x); 12 } 13 14 public void pop() { 15 // if pop operation could result in the changing of the current minimum value, 16 // pop twice and change the current minimum value to the last minimum value. 17 if(stack.pop() == min) min=stack.pop(); 18 } 19 20 public int top() { 21 return stack.peek(); 22 } 23 24 public int getMin() { 25 return min; 26 } 27 }
相关文章
- java:stack栈: Stack 类表示后进先出(LIFO)的对象堆栈
- Java实现 LeetCode 806 写字符串需要的行数 (暴力模拟)
- Java实现 LeetCode 740 删除与获得点数(递推 || 动态规划?打家劫舍Ⅳ)
- Java实现 LeetCode 617 合并二叉树(遍历树)
- Java实现 LeetCode 552 学生出勤记录 II(数学转换?还是动态规划?)
- Java实现 LeetCode 514 自由之路
- Java实现 LeetCode 449 序列化和反序列化二叉搜索树
- Java实现 LeetCode 8 字符串转换整数(atoi)
- 【二叉搜索树】LeetCode 98. 验证二叉搜索树【中等】
- LeetCode-436. 寻找右区间【双指针】
- 1143. 最长公共子序列——【Leetcode每日刷题】
- leetcode 30. 串联所有单词的子串----滑动窗口篇八
- LeetCode[155]-Min Stack
- LeetCode: Surrounded Regions [130]
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found
- LeetCode 142. 环形链表 II