LeetCode第155题 最小栈
生活随笔
收集整理的這篇文章主要介紹了
LeetCode第155题 最小栈
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
設(shè)計一個支持 push，pop，top 操作，并能在常數(shù)時間內(nèi)檢索到最小元素的棧。
push(x) -- 將元素 x 推入棧中。
pop() -- 刪除棧頂?shù)脑亍?/span>
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.
思路: 使用太多封裝雖然偷了懶,效率影響確實很大...
使用兩個棧,一個保存真實的數(shù)據(jù),另一個保存所有最小值
eg:
push : -1 0 -2 3 4
push操作完成后,兩個棧的情況如下:
stack: -1 0 -2 3 4
minData: -1 -2
只要當(dāng)前mindata的top(-2)未被彈出,棧中的最小值就一直是-2.
如果此時stack彈出的值為(-2),那么mindata中的值也要更新,將-2彈出.
那么此時
stack: -1 0
minData: -1
棧中的最小值就為-1了
1 class MinStack { 2 3 /** 4 * initialize your data structure here. 5 */ 6 private Stack<Integer> stack; //棧 7 private Stack<Integer> minData; //保存最小值的棧 8 9 public MinStack() { 10 11 stack = new Stack<>(); 12 minData = new Stack<>(); 13 } 14 15 public void push(int x) { 16 stack.push(x); 17 if (minData.empty() || minData.peek() >= x) { 18 minData.push(x); 19 } 20 } 21 22 public void pop() { 23 if (stack.peek().equals(minData.peek())) { 24 minData.pop(); 25 } 26 stack.pop(); 27 } 28 29 public int top() { 30 return stack.peek(); 31 } 32 33 public int getMin() { 34 return minData.peek(); 35 } 36 }
push(x) -- 將元素 x 推入棧中。
pop() -- 刪除棧頂?shù)脑亍?/span>
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.
思路: 使用太多封裝雖然偷了懶,效率影響確實很大...
使用兩個棧,一個保存真實的數(shù)據(jù),另一個保存所有最小值
eg:
push : -1 0 -2 3 4
push操作完成后,兩個棧的情況如下:
stack: -1 0 -2 3 4
minData: -1 -2
只要當(dāng)前mindata的top(-2)未被彈出,棧中的最小值就一直是-2.
如果此時stack彈出的值為(-2),那么mindata中的值也要更新,將-2彈出.
那么此時
stack: -1 0
minData: -1
棧中的最小值就為-1了
1 class MinStack { 2 3 /** 4 * initialize your data structure here. 5 */ 6 private Stack<Integer> stack; //棧 7 private Stack<Integer> minData; //保存最小值的棧 8 9 public MinStack() { 10 11 stack = new Stack<>(); 12 minData = new Stack<>(); 13 } 14 15 public void push(int x) { 16 stack.push(x); 17 if (minData.empty() || minData.peek() >= x) { 18 minData.push(x); 19 } 20 } 21 22 public void pop() { 23 if (stack.peek().equals(minData.peek())) { 24 minData.pop(); 25 } 26 stack.pop(); 27 } 28 29 public int top() { 30 return stack.peek(); 31 } 32 33 public int getMin() { 34 return minData.peek(); 35 } 36 }
?
轉(zhuǎn)載于:https://www.cnblogs.com/rainbow-/p/10390860.html
總結(jié)
以上是生活随笔為你收集整理的LeetCode第155题 最小栈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： [Lintcode]41. Maximu
- 下一篇： 记账本小程序7天开发记录（第二天）