【面試算法】一個有getMin功能的棧

he_xd 發布于2019-08-14 15:17 / 1924人閱讀

摘要：題目實現一個特殊的棧，在實現棧的基本功能上再實現一個實現返回棧中最小元素的操作。要求，操作的時間復雜度都是，設計的棧類型額可以使用現成的棧結構。第一種代碼實現第二種代碼實現

【題目】實現一個特殊的棧，在實現棧的基本功能上再實現一個實現返回棧中最小元素的操作。
【要求】
1，pop、push、getMin操作的時間復雜度都是O（1）；
2，設計的棧類型額可以使用現成的棧結構。

第一種代碼實現：

public class GetMinStack_1 {

    private Stack stackData;
    private Stack stackMin;

    public GetMinStack_1(){
        stackData = new Stack();
        stackMin = new Stack();
    }

    public void push(int newNum){
        if (stackMin.isEmpty()) {
            stackMin.push(newNum);
        }else if (newNum <= getMin()) {
            stackMin.push(newNum);
        }
        stackData.push(newNum);
    }

    public int pop(){
        if (stackData.isEmpty()) {
            System.out.println("stack is empty");
            return -1;
        }
        int value = stackData.pop();
        if (value == getMin()) {
            stackMin.pop();
        }
        return value;
    }

    private int getMin() {
        // TODO Auto-generated method stub
        if (stackMin.isEmpty()) {
            System.out.println("stack is empty");
            return -1;
        }
        return stackMin.peek();
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        GetMinStack_1 stack = new GetMinStack_1();
        int[] testNum = {4,2,4,6,5,0,1,10};
        for(int i:testNum){
            stack.push(i);
        }
        for(int i = 0; i < testNum.length; i++){
            System.out.println(stack.getMin()+" "+stack.pop());
        }
    }

}

第二種代碼實現：

public class GetMinStack_2 {

    private Stack stackData;
    private Stack stackMin;

    public GetMinStack_2(){
        stackData = new Stack();
        stackMin = new Stack();
    }

    public void push(int newNum){
        if (stackMin.isEmpty()) {
            stackMin.push(newNum);
        }
        else if (newNum <= getMin()) {
            stackMin.push(newNum);
        }else {
            stackMin.push(getMin());
        }
        stackData.push(newNum);
    }

    public int pop(){
        if (stackData.isEmpty()) {
            System.out.println("stack is empty");
            return -1;
        }
        int value = stackData.pop();
        stackMin.pop();
        return value;
    }

    private int getMin() {
        // TODO Auto-generated method stub
        if (stackMin.isEmpty()) {
            System.out.println("stack is empty");
            return -1;
        }
        return stackMin.peek();
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        GetMinStack_2 stack = new GetMinStack_2();
        int[] testNum = {4,2,4,6,5,0,1,10};
        for(int i:testNum){
            stack.push(i);
        }
        for(int i = 0; i < testNum.length; i++){
            System.out.println(stack.getMin()+" "+stack.pop());
        }
    }
}

云服務器 GPU云服務器面試一個php 自然語言處理算法面試字符串算法面試題面試c語言算法編程題

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65579.html

【刷算法】LeetCode.155-最小棧

摘要：題目描述設計一個支持，，操作，并能在常數時間內檢索到最小元素的棧。刪除棧頂的元素。檢索棧中的最小元素。示例返回返回返回代碼實現題目描述設計一個支持 push，pop，top 操作，并能在常數時間內檢索到最小元素的棧。 push(x) -- 將元素 x 推入棧中。 pop() -- 刪除棧頂的元素。 top() -- 獲取棧頂元素。 getMin() -- 檢索棧中的最小元素。示例...

wing324 2019-08-23 11:31 評論0 收藏0
LeetCode 155：最小棧 Min Stack

摘要：刪除棧頂的元素。可以另外新建一個棧來順序存入數據最小值。另外在數據入棧時需要判斷該值是否比輔助棧的棧頂元素的值更小，如果更小，也應該將它加入輔助棧。并且需要判斷輔助棧是否為空，在不空的條件下才可以取棧頂元素比較，否則會溢出。 LeetCode 155：最小棧 Min Stack 設計一個支持 push，pop，top 操作，并能在常數時間內檢索到最小元素的棧。 push(x) -- ...

LeexMuller 2019-08-19 10:16 評論0 收藏0
【Java】幾道常見的秋招面試題

摘要：總結的時間復雜度是，是空間是使用輔助棧來存儲最小值。項目就是為了解決配置繁瑣的問題，最大化的實現約定大于配置。前言只有光頭才能變強 Redis目前還在看，今天來分享一下我在秋招看過(遇到)的一些面試題(相對比較常見的) 0、final關鍵字簡要說一下final關鍵字，final可以用來修飾什么？這題我是在真實的面試中遇到的，當時答得不太好，現在來整理一下吧。 final可以修飾...

Rocko 2019-08-16 13:29 評論0 收藏0
力扣(LeetCode)155

摘要：題目地址題目描述設計一個支持，，操作，并能在常數時間內檢索到最小元素的棧。將元素推入棧中。刪除棧頂的元素。示例返回返回返回解答每次入棧都放入兩個元素，分別是當前元素，和當前的最小元素因此放入之前需要和當前值進行比較。題目地址：https://leetcode-cn.com/probl...題目描述：設計一個支持 push，pop，top 操作，并能在常數時間內檢索到最小元素的棧。 p...

Scliang 2019-08-16 15:21 評論0 收藏0