栈的min函数以及出栈和入栈序列判断-剑指offer

电玩女神 2021-12-10 22:51 206阅读 0赞

### **1、****题目****描述** ###

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。在该栈中调用push、pop、top、min的时间复杂度都是o(1)。

**解题思路：**运用一个辅助栈，用于存储当前数据最小的数，当最小元素栈没有元素的时候直接放入数据，

当有元素的时候进行比较是不是来的数据比最小栈中的数据小，如果进来的数据更小，就入栈最小数据栈中，否则就不入最小数据栈。

stackMin.push(stackMin.isEmpyt()? data:Math.min(data,stackMin.peek()))。

剑指offer代码：

> 1.  import java.util.Stack;
> 2.  public class Solution \{
> 3.      Stack<Integer> stack = new Stack<Integer>();
> 4.      Stack<Integer> stackMin = new Stack<Integer>();
> 5.      public void push(int node) \{
> 6.          stack.push(node);
> 7.          stackMin.push(stackMin.isEmpty()?node:Math.min(node,stackMin.peek()));
> 8.      \}
> 9.      
> 10.     public void pop() \{
> 11.         stack.pop();
> 12.         stackMin.pop();
> 13.     \}
> 14.     
> 15.     public int top() \{
> 16.         return stack.peek();
> 17.     \}
> 18.     public int min() \{
> 19.         return stackMin.peek();
> 20.     \}
> 21. \}

本机测试代码如下：

> 1.  package pratice618;
> 2.  import java.util.Stack;
> 3.  //题目说明：定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
> 4.  //  在该栈中调用push、pop、top、min的时间复杂度都是o(1)。
> 5.  //解题思路：运用一个辅助栈，用于存储当前数据最小的数，当最小元素栈没有元素的时候直接放入数据，
> 6.  //  当有元素的时候进行比较是不是来的数据比最小栈中的数据小，如果进来的数据更小，就入栈最小数据栈中，否则就不入最小数据栈。
> 7.  //   stackMin.push(stackMin.isEmpyt()? data:Math.min(data,stackMin.peek()))
> 8.  public class StackMin30\_711 \{
> 9.      static Stack<Integer> stack = new Stack<Integer>();
> 10.     static Stack<Integer> stackMin = new Stack<Integer>();
> 11.     public static void push(int data)\{
> 12.         stack.push(data);
> 13.         stackMin.push(stackMin.isEmpty()? data:Math.min(data, stackMin.peek()));
> 14.     \}
> 15.     public void pop()\{
> 16.         stack.pop();
> 17.         stackMin.pop();
> 18.     \}
> 19.     public static int min()\{
> 20.         return stackMin.peek();
> 21.     \}
> 22.     public static void main(String\[\] args) \{
> 23.         int data\[\] = \{12,4,5,7,2,6,3\};
> 24.         for(int i=0;i<data.length;i++)
> 25.         \{
> 26.             push(data\[i\]);
> 27.         \}
> 28.         int minS = min();
> 29.         System.out.print("minS "+minS);
> 30.     \}
> 31. \}

### **2、题目描述** ###

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。

例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。

**解题思路：**出栈可能的个数：n=(2n!) / (n! \* (n+1)!).

出栈的每个元素后面比该元素的原下标小的元素，应该按原下标从大到小的相对顺序排列。

根据两个队列进行出栈操作，看是否符合，最终栈是否为空。

> 1.  package pratice618;
> 2.  import java.util.Stack;
> 3.  public class StackPopPush31\_711 \{
> 4.  //题目说明：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
> 5.  //  例如序列 1,2,3,4,5 是某栈的压入顺序，序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。
> 6.  //解题思路：出栈可能的个数：n=(2n!) / (n! \* (n+1)!)
> 7.  //  出栈的每个元素后面比该元素的原下标小的元素，应该按原下标从大到小的相对顺序排列
> 8.  //  根据两个队列进行出栈操作，看是否符合，最终栈是否为空
> 9.      public static boolean stackPopPush(int pop\[\],int push\[\])\{
> 10.         Stack<Integer> stack = new Stack();
> 11.         for(int popI=0,pushI=0; pushI<push.length; pushI++)
> 12.         \{
> 13.             stack.push(push\[pushI\]);
> 14.             while(popI<push.length && !stack.isEmpty() && stack.peek() == pop\[popI\])
> 15.             \{
> 16.                 stack.pop();
> 17.                 popI++;
> 18.             \}
> 19.         \}
> 20.         return stack.isEmpty();
> 21.     \}
> 22.     public static void main(String\[\] args) \{
> 23.         int push\[\] = \{2,3,4,5,6\};//输入
> 24.         int pop\[\] = \{2,4,5,3,6\};//输出
> 25.         boolean result = stackPopPush(pop,push);
> 26.         System.out.print("result: "+ result);
> 27.     \}
> 28. \}

### **扫码关注一起随时随地学习！！！就在洋葱攻城狮，更多精彩，等你来！！** ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3ljeTA3MDY_size_16_color_FFFFFF_t_70]: /images/20211210/fb8174ad02f34ed69838d8a420dd3a5c.png