劍指Offer系列(java版,詳細解析)30.包含min函數的棧

程序員社區 2022-01-08 02:58:27 阅读数:209

offer 系列 java 解析 包含

題目描述

劍指 Offer 30. 包含min函數的棧

定義棧的數據結構,請在該類型中實現一個能够得到棧的最小元素的 min 函數在該棧中,調用 min、push 及 pop 的時間複雜度都是 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.

提示:

  1. 各函數的調用總次數不超過 20000 次

測試用例

  • 新壓入棧的數字比之前的最小值大。
  • 新壓入棧的數字比之前的最小值小。
  • 彈出棧的數字不是最小元素。
  • 彈出棧的數字是最小元素。

題目考點

  • 考察應聘者分析複雜問題的思維能力——舉例分析。
  • 考察應聘者對棧的理解。

解題思路

這裏只限制了時間複雜度,沒限制空間複雜度,我們可能會想到用輔助棧。

然後我們就會想到用一個棧來保存最小值,具體怎麼保存?

我們可以每次在輔助棧都壓入當前數據棧的最小值。在執行min函數的時候直接取到輔助棧的棧頂元素即可,當執行push函數時,如果壓入的元素比當前最小值小則壓入輔助棧,不然再壓入一個當前最小值(為了pop的方便),在執行pop函數時,我們只要直接彈出數據棧與輔助棧的棧頂元素就好。

參考解題

class MinStack {
 Stack<Integer> stack1 ; Stack<Integer> stack2 ; /** initialize your data structure here. */ public MinStack() {
 stack1 = new Stack(); stack2 = new Stack(); } public void push(int x) {
 if(stack2.isEmpty() || stack2.peek()>=x) stack2.push(x); stack1.push(x); } public void pop() {
 if(!stack2.isEmpty() && stack1.peek()<=stack2.peek()) stack2.pop(); stack1.pop(); } public int top() {
 return stack1.isEmpty() ? 0 : 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(); */
版权声明:本文为[程序員社區]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201080258269906.html