1 题目:

实现一个栈, 该栈带有出栈(pop), 入栈(push), 取最小元素(getMin)3个方法. 并且要保证3个方法的时间复杂度都是O(1)

2 思路:

  1.   1.创建两个栈, 栈A和备胎栈B, 并且我们的目标是让所有的最小元素全部存放在栈B.<br />                 2.第一个元素进入栈A, 此时只有一个元素, 最小元素就是第一个元素,   所以, 让新元素也进入栈B.


3.每当有新元素进入栈A, 则新元素和A的最小值进行比较, 即和栈B的栈顶元素比较, 如果小于B的栈 顶元素, 则让其进行栈B.那么此时栈B的栈顶元素就是栈A的最小元素值
image-20210426201749238.png
(3) 时间复杂度: 进栈, 出栈, 取最小值的时间复杂度都是O(1)


空间复杂度: 最坏情况的空间复杂度是O(n)

3.代码

  1. package com.xiaoxuanfeng.arithmetic;
  3. import java.util.Stack;
  5. // 最小栈的实现
  6. public class TheRealizationOfSmallestStack {
  7.     // 1.创建两个栈, 一个主栈 mainStack, 一个辅肋栈minStack
  8.     Stack<Integer> mainStack = new Stack<>();
  9.     Stack<Integer> minStack = new Stack<>();
  11.     // 2.入栈方法
  12.     public void push(int element) {
  13.         mainStack.push(element);
  14.         // 如果minStack 为空, 或者element <= minStack.peek()
  15.         if (minStack.isEmpty() || element <= minStack.peek()) {
  16.             minStack.push(element);
  17.         }
  18.     }
  20.     // 3.出栈方法
  21.     public void pop() {
  22.         // 如果主栈当前的栈顶元素 == 辅助的栈顶元素,
  23.         if (mainStack.peek() == minStack.peek()) {
  24.             minStack.pop();
  25.         }
  26.         mainStack.pop();
  27.     }
  29.     // 4.取最小值方法
  30.     public int getMin() throws Exception {
  31.         // 首先判断主栈是否为空
  32.         if (mainStack.isEmpty()) {
  33.             throw new Exception("mainStack is empty");
  34.         }
  35.         return minStack.peek();
  36.     }
  38.     // 5.测试
  39.     public static void main(String[] args) throws Exception {
  40.         // 创建最小栈
  41.         TheRealizationOfSmallestStack minStack = new TheRealizationOfSmallestStack();
  42.         minStack.push(8);
  43.         minStack.push(2);
  44.         minStack.push(3);
  46.         minStack.pop();
  48.         // 打印结果
  49.         System.out.println("最小栈的目前最小值是:" + minStack.getMin());
  50.     }
  52. }