[[437859]]

本文轉(zhuǎn)載自微信公眾號(hào)「程序員千羽」，作者程序員千羽 。轉(zhuǎn)載本文請(qǐng)聯(lián)系程序員千羽公眾號(hào)。

Leetcode : https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof

“GitHub : https://gitee.com/nateshao/leetcode/blob/main/algo-notes/src/main/java/com/nateshao/sword_offer/topic_23_MinStack/MinStack.java

包含min函數(shù)的棧

“題目描述 ：定義棧的數(shù)據(jù)結(jié)構(gòu)，請(qǐng)?jiān)谠擃?lèi)型中實(shí)現(xiàn)一個(gè)能夠得到棧的最小元素的 min 函數(shù)在該棧中，調(diào)用 min、push 及 pop 的時(shí)間復(fù)雜度都是 O(1)。示例：

MinStack minStack = new MinStack(); 
minStack.push(-2); 
minStack.push(0); 
minStack.push(-3); 
minStack.min();   --> 返回 -3. 
minStack.pop(); 
minStack.top();   --> 返回 0. 
minStack.min();   --> 返回 -2. 

• 提示：

各函數(shù)的調(diào)用總次數(shù)不超過(guò) 20000 次

解題思路： 定義兩個(gè)棧，一個(gè)存放入的值。另一個(gè)存最小值。

“普通棧的 push() 和 pop() 函數(shù)的復(fù)雜度為 O(1) ;而獲取棧最小值 min() 函數(shù)需要遍歷整個(gè)棧，復(fù)雜度為 O(N) 。

• 本題難點(diǎn):將min() 函數(shù)復(fù)雜度降為0(1)，可通過(guò)建立輔助棧實(shí)現(xiàn);
  • 數(shù)據(jù)棧A：棧A用于存儲(chǔ)所有元素，保證入棧push() 函數(shù)、出棧pop() 函數(shù)、獲取棧頂top()函數(shù)的正常邏輯。
  • 輔助棧B：棧B中存儲(chǔ)棧A中所有非嚴(yán)格降序的元素，則棧A中的最小元素始終對(duì)應(yīng)棧B的棧頂元素，即min() 函數(shù)只需返回棧B的棧頂元素即可。

因此,只需設(shè)法維護(hù)好棧B的元素，使其保持非嚴(yán)格降序,即可實(shí)現(xiàn)min() 函數(shù)的0(1)復(fù)雜度。

函數(shù)設(shè)計(jì)：

• push(x) 函數(shù)： 重點(diǎn)為保持棧 B 的元素是 非嚴(yán)格降序 的。
  • 將 x 壓入棧 A(即 A.add(x) );
  • 若 ① 棧 B 為空 或 ② x 小于等于 棧 B 的棧頂元素，則將 x 壓入棧 B (即 B.add(x) )。
• pop() 函數(shù)： 重點(diǎn)為保持棧 A, B 的 元素一致性 。
  • 執(zhí)行棧 A 出棧(即 A.pop() )，將出棧元素記為 y ;
  • 若 y 等于棧 B 的棧頂元素，則執(zhí)行棧 B 出棧(即 B.pop() )。
• top() 函數(shù)： 直接返回棧 A 的棧頂元素即可，即返回 A.peek() 。
• min() 函數(shù)： 直接返回棧 B 的棧頂元素即可，即返回 B.peek() 。

復(fù)雜度分析：

• 時(shí)間復(fù)雜度 O(1) ： push(), pop(), top(), min() 四個(gè)函數(shù)的時(shí)間復(fù)雜度均為常數(shù)級(jí)別。
• 空間復(fù)雜度 O(N) ： 當(dāng)共有 N個(gè)待入棧元素時(shí)，輔助棧 B最差情況下存儲(chǔ) N 個(gè)元素，使用 O(N)額外空間。

“Java 代碼中，由于 Stack 中存儲(chǔ)的是 int 的包裝類(lèi) Integer ，因此需要使用 equals() 代替 == 來(lái)比較值是否相等。此題如果用==將會(huì)無(wú)法通過(guò) Integer的equals重寫(xiě)過(guò)，比較的是內(nèi)部value的值， ==如果在[-128,127]會(huì)被cache緩存,超過(guò)這個(gè)范圍則比較的是對(duì)象是否相同

package com.nateshao.sword_offer.topic_23_MinStack; 
 
import java.util.Stack; 
 
/** 
 * @date Created by 邵桐杰 on 2021/11/28 21:38 
 * @微信公眾號(hào) 程序員千羽 
 * @個(gè)人網(wǎng)站 www.nateshao.cn 
 * @博客 https://nateshao.gitee.io 
 * @GitHub https://github.com/nateshao 
 * @Gitee https://gitee.com/nateshao 
 * Description: 包含min函數(shù)的棧 
 * 思路：定義兩個(gè)棧，一個(gè)存放入的值。另一個(gè)存最小值。 
 */ 
public class MinStack { 
    private Stack<Integer> stack1; // 數(shù)據(jù)棧 
    private Stack<Integer> stack2; // 輔助棧，記錄每次有元素進(jìn)棧后或者出棧后，元素的最小值 
 
    /** 
     * initialize your data structure here. 
     */ 
    public MinStack() { 
        // 初始化輔助棧和數(shù)據(jù)棧 
        stack1 = new Stack<>(); 
        stack2 = new Stack<>(); 
    } 
 
    public void push(int x) { 
        // 數(shù)據(jù)棧，進(jìn)棧 
        stack1.push(x); 
        // 如果記錄當(dāng)前數(shù)據(jù)棧中最小值的輔助棧為空，或者最小值小于 x，則將 x 設(shè)置為最小值，即進(jìn)輔助棧 
        if (stack2.isEmpty() || stack2.peek() >= x) stack2.push(x); 
    } 
 
    public void pop() { 
        if (stack1.pop().equals(stack2.peek())) stack2.pop(); 
    } 
 
    public int top() { 
        return stack1.peek(); 
    } 
 
    public int min() { 
        return stack2.peek(); 
    } 
 
    /** 
     * Your MinStack object will be instantiated and called as such: 
     * MinStack obj = new MinStack(); 
     * obj.push(x); 
     * obj.pop(); 
     * int param_3 = obj.top(); 
     * int param_4 = obj.min(); 
     */ 
 
    /** 
     * 精選解答 
     */ 
    class MinStack1 { 
 
        Stack<Integer> A, B; 
 
        public MinStack1() { 
            A = new Stack<>(); 
            B = new Stack<>(); 
        } 
 
        public void push(int x) { 
            A.add(x); 
            if (B.empty() || B.peek() >= x) 
                B.add(x); 
        } 
 
        public void pop() { 
            if (A.pop().equals(B.peek())) 
                B.pop(); 
        } 
 
        public int top() { 
            return A.peek(); 
        } 
 
        public int min() { 
            return B.peek(); 
        } 
    } 
} 

參考鏈接：https://leetcode-cn.com/problems/bao-han-minhan-shu-de-zhan-lcof/solution