微軟算法100題02設計包含min函數的棧

2019-11-14 15:22:04

字體：大中小

來源：轉載

供稿：網友

要求：
1. 定義棧的數據結構，要求添加一個 min函數，能夠得到棧的最小元素
2. 要求函數 min、push 以及 pop 的時間復雜度都是 O(1)

思路: 構建一個輔助棧, 只有當前入棧的數據小于該輔助棧的棧頂元素時，才將其push到輔助棧, 保證輔助棧的棧頂元素總為最小，當出棧時，如果出棧元素大于輔助棧棧頂元素，則該元素必然不在輔助棧中，因為輔助棧保留了原始棧的入棧順序(只按大到小存儲舍棄了一些元素), 該較大元素在入棧時就已經被輔助棧過濾掉了，如果出棧元素小于或等于輔助棧棧頂元素，則輔助棧也進行pop操作

 1 package com.rui.microsoft; 2  3 import java.util.Stack; 4  5 public class Test02_MinStack { 6  7     public static void main(String[] args) { 8         MyStack myStack = new MyStack(); 9         myStack.push(5);10         myStack.push(3);11         myStack.push(1);12         myStack.push(6);13         14         System.out.PRintln(myStack.min());15         16         myStack.pop();17         System.out.println(myStack.min());18         19         myStack.pop();20         System.out.println(myStack.min());21         22     }23     24     static class MyStack{25         private Stack<Integer> stack = new Stack<Integer>();26         private Stack<Integer> minStack = new Stack<Integer>();27         28         public void push(int i){29             stack.push(i);30             31             if(minStack.isEmpty()){32                 minStack.push(i);33             }else{34                 int min = minStack.peek();35                 //minStack only push item smaller than its top item36                 //minStack只入棧比其棧頂元素小的元素37                 if(i < min){38                     minStack.push(i);39                 }40             }41         }42         43         public Integer pop(){44             Integer i = stack.pop();45             //when pop an item from original stack46             //we need to process the minStack also47             //if the item popped from original stack is larger than minStack's top item48             //it means this item should not exist in minStack49             if(i <= minStack.peek()){50                 minStack.pop();51             }52             return i;53         }54         55         public Integer min(){56             return minStack.peek();57         }58     }59 }