每天一道劍指offer-包含min函數的棧

• 2019 年 10 月 4 日
• 筆記

前言

今天的題目 每天的題目見github(看最新的日期): https://github.com/gzc426 具體的題目可以去牛客網對應專題去找。

昨天的題解

題目

每天一道劍指offer-包含min函數的棧 來源：牛客網對應專題

題目詳述

定義棧的數據結構，請在該類型中實現一個能夠得到棧中所含最小元素的min函數（時間複雜度應為O（1））。

題目詳解

思路

• 利用一個輔助棧來存放最小值
• 棧 3，4，2，5，1
• 輔助棧 3，3，2，2，1
• 每入棧一次，就與輔助棧頂比較大小，如果小就入棧，如果大就入棧當前的輔助棧頂 當出棧時，輔助棧也要出棧
• 棧3 輔助棧入3，
• 棧4，輔助棧棧頂比4小入3，
• 棧入2，輔助棧棧頂是3比2大所以入2，每次都是把棧頂與入棧的值比較，入那個最小的，這樣棧頂一直最小。

程式碼

import java.util.Stack;  public class Solution {      Stack<Integer> stack1 = new Stack<>();      Stack<Integer> stack2 = new Stack<>();      public void push(int node) {          stack1.push(node);          if(stack2.empty())          {              stack2.push(node);          }else{              if(node <= (int)stack2.peek()) //這個if/else是比較棧頂與入棧的值，哪個小入哪個                  stack2.push(node);              else{                  stack2.push(stack2.peek());              }          }      }      public void pop() {          stack2.pop();//出棧是都出棧的          stack1.pop();      }        public int top() {          return (int)stack1.peek();      }        public int min() {          return (int)stack2.peek();//棧2是輔助棧，每次都是最小值      }  }

程式碼截圖（避免亂碼）