定義棧的數據結構,請在該類型中實現一個能夠得到棧最小元素的min函數。要求:使得時間復雜度都是O(1)
完成如下的函數:
import java.util.Stack;public class Solution { public void push(int node) { } public void pop() { } public int top() { } public int min() { }}思路:用空間換時間,用一個輔助棧記錄當前棧中的最小值。輔助棧元素個數和數據棧保持一樣的數目。例如一次壓入數據棧數字序列為:
3,2,4,1,5 那么一次壓入輔助棧的為:3,2,2,1,1
當每次壓入數據棧的元素小余輔助站的元素的時候,才把新元素壓入輔助棧,否則把輔助站棧頂元素去到壓入輔助棧,保持兩個棧元素個數一致。
備注:Stack.Peek 與 stack.pop 的區別
相同點:大家都返回棧頂的值。
不同點:peek 不改變棧的值(不刪除棧頂的值),pop會把棧頂的值刪除。
package com.mytest.mymain;import java.util.Stack;public class MinStack { PRivate Stack<Integer> data_stack=new Stack<Integer>(); private Stack<Integer> min_stack=new Stack<Integer>(); public void push(int node) {//進棧 if(min_stack.isEmpty() ||min_stack.peek()>=node){ min_stack.push(node); }else{ min_stack.push(min_stack.peek()); } data_stack.push(node); } public void pop() {//出棧 if(data_stack.empty() || min_stack.empty()) return; data_stack.pop(); min_stack.pop(); } public int top() {//取得棧頂元素 if(!data_stack.empty()){ return data_stack.peek(); } return 0; } public int min() {//取得最小值 if(!min_stack.empty()){ return min_stack.peek(); } return 0; }}
新聞熱點
疑難解答