題目描述

最小棧
設(shè)計(jì)一個(gè)支持 push ，pop ，top 操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。

push(x) —— 將元素 x 推入棧中。
pop() —— 刪除棧頂?shù)脑亍?br> top() —— 獲取棧頂元素。
getMin() —— 檢索棧中的最小元素。

示例:
輸入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
輸出：
[null,null,null,null,-3,null,0,-2]

解釋：
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ù)結(jié)構(gòu)

• 數(shù)組（棧）、鏈表（鏈棧）

算法思維

• 遍歷、狀態(tài)機(jī)、快照、棧特性（LIFO）

解題要點(diǎn)

• 使用快照記錄狀態(tài)信息
• 利用棧的 LIFO 特性，實(shí)現(xiàn)狀態(tài)信息的 更新/回滾

解題思路

一. Comprehend 理解題意

• 需要自實(shí)現(xiàn)一個(gè)棧結(jié)構(gòu)
• 除了基礎(chǔ)的入棧、出棧、查看棧頂功能外，還需要實(shí)現(xiàn)一個(gè)查詢最小值的功能

二. Choose 選擇數(shù)據(jù)結(jié)構(gòu)與算法

解法一：使用數(shù)組實(shí)現(xiàn)棧結(jié)構(gòu)，棧的最小值通過(guò)遍歷數(shù)組獲得

• 數(shù)據(jù)結(jié)構(gòu)：數(shù)組
• 算法思維：遍歷

三. Code 編碼實(shí)現(xiàn)基本解法

class MinStack {

        //1.聲明存放數(shù)據(jù)的數(shù)組和棧頂指針
        Integer[] arr;
        int index;

        /**
         * initialize your data structure here.
         */
        public MinStack() {
            //2.構(gòu)造器中進(jìn)行參數(shù)初始化
            arr = new Integer[1000];
            index = -1;
        }

        public void push(int x) {
            //3.入棧 -- 自動(dòng)裝箱
            arr[++index] = x;

            //數(shù)組擴(kuò)容
            if (index == arr.length*0.8){
                Integer[] arr1 = new Integer[arr.length*2];
                for (int i=0; i<arr.length; i++){
                    arr1[i] = arr[i];
                }
                arr = arr1;
            }
        }

        public void pop() {
            if(index < 0) return;
            //4.出棧 -- 相當(dāng)于刪除棧頂元素 -- 棧頂賦值為 null
            arr[index--] = null;
        }

        public int top() {
            if (index < 0) return Integer.parseInt(null);
            //5.返回棧頂元素 -- 自動(dòng)拆箱
            return arr[index];
        }

        public int getMin() {
            if (index < 0) return Integer.parseInt(null);

            //6.遍歷數(shù)組尋找最小值
            int minus = arr[0]; //最小值
            for (int i=1; i<=index; i++){
                minus = arr[i] < minus ? arr[i] : minus;
            }
            return minus;
        }
    }

執(zhí)行耗時(shí)：65 ms，擊敗了 7.35% 的Java用戶
內(nèi)存消耗：40.2 MB，擊敗了 55.30% 的Java用戶
時(shí)間復(fù)雜度：O(n) -- 數(shù)組的遍歷 O(n)，數(shù)組的擴(kuò)容 O(n)
空間復(fù)雜度：O(n) -- 數(shù)組的內(nèi)存空間 O(n)

四. Consider 思考更優(yōu)解

改變算法思維！

思路：

• 每次獲取最小值時(shí)，都需要重新 遍歷 數(shù)組，效率很低
• 不難發(fā)現(xiàn)，每個(gè)元素在被壓入棧頂?shù)臅r(shí)候，棧的最小值都只有 兩種狀態(tài) ：
  1.當(dāng)前元素為最小值（狀態(tài)一：某個(gè)新的數(shù)值）
  2.以前的最小值仍為最小值（狀態(tài)二：原數(shù)值）
• 能否利用棧的特性，彈出棧頂元素的時(shí)候，將最小值的狀態(tài)變化也一并彈出？

方法：

• 讓每個(gè)元素都攜帶一個(gè)“快照”，記錄此元素入棧后（這一時(shí)刻）棧的最小值。
• 當(dāng)前棧的最小值 == 當(dāng)前棧頂元素快照中的值
• 當(dāng)棧頂元素被彈出，上個(gè)元素成為棧頂，上個(gè)快照被啟用，最小值回滾

解法二：使用鏈表實(shí)現(xiàn)棧結(jié)構(gòu)，棧的最小值由棧頂元素?cái)y帶

• 數(shù)據(jù)結(jié)構(gòu)：鏈表（鏈棧）
• 算法思維：狀態(tài)機(jī)、快照、棧特性（LIFO）

五. Code 編碼實(shí)現(xiàn)最優(yōu)解

 class MinStack {

        //1.聲明一個(gè)內(nèi)部類 -- 鏈表節(jié)點(diǎn)
        private class Node{
            int val; //當(dāng)前節(jié)點(diǎn)值
            int min; //最小值快照 -- 當(dāng)前節(jié)點(diǎn)入棧后，棧的最小值

            Node next; //指針

            public Node(){}

            public Node(int val, int min, Node next){
                this.val = val;
                this.min = min;
                this.next = next;
            }
        }

        //2.聲明一個(gè)鏈表頭 -- 棧頂
        Node head;

        /**
         * initialize your data structure here.
         */
        public MinStack() {
            //3.初始化鏈棧
            head = null;
        }

        public void push(int x) {
            //4.節(jié)點(diǎn)入棧時(shí)，判斷鏈表長(zhǎng)度
            if (head == null) {
                head = new Node(x,x,null);
            } else {
                //5.每次入棧時(shí)，比較最小值，將此刻的最小值存入 new Node().min 中
                head = new Node(x,Math.min(x,head.min),head);
            }
        }

        public void pop() {
            //6.出棧時(shí)，直接彈出即可，最小值隨之回滾
            if (head != null) head = head.next;
        }

        public int top() {
            //7.查棧頂
            return head != null ? head.val : Integer.parseInt(null);
        }

        public int getMin() {
            //8.查最小值 -- 其實(shí)就是查當(dāng)前棧頂?shù)淖钚≈悼煺?            return head != null ? head.min : Integer.parseInt(null);
        }
    }

執(zhí)行耗時(shí)：6 ms，擊敗了 96.02% 的Java用戶
內(nèi)存消耗：40.3 MB，擊敗了 36.21% 的Java用戶
時(shí)間復(fù)雜度：O(1) -- 棧頂元素的直接查詢 O(1)
空間復(fù)雜度：O(n) -- 鏈棧的內(nèi)存空間 O(n)

六. Change 變形與延伸

=== 待續(xù) ===