算法 1.3.1 最小栈 【leetcode 155】

题目描述

最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。

示例:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

数据结构

• 数组（栈）、链表（链栈）

算法思维

• 遍历、状态机、快照、栈特性（LIFO）

解题要点

• 使用快照记录状态信息
• 利用栈的 LIFO 特性，实现状态信息的 更新/回滚

---

解题思路

一. Comprehend 理解题意

• 需要自实现一个栈结构
• 除了基础的入栈、出栈、查看栈顶功能外，还需要实现一个查询最小值的功能

二. Choose 选择数据结构与算法

解法一：使用数组实现栈结构，栈的最小值通过遍历数组获得

• 数据结构：数组
• 算法思维：遍历

三. Code 编码实现基本解法

class MinStack {

        //1.声明存放数据的数组和栈顶指针
        Integer[] arr;
        int index;

        /**
         * initialize your data structure here.
         */
        public MinStack() {
            //2.构造器中进行参数初始化
            arr = new Integer[1000];
            index = -1;
        }

        public void push(int x) {
            //3.入栈 -- 自动装箱
            arr[++index] = x;

            //数组扩容
            if (index == arr.length*0.8){
                Integer[] arr1 = new Integer[arr.length*2];
                for (int i=0; i<arr.length; i++){
                    arr1[i] = arr[i];
                }
                arr = arr1;
            }
        }

        public void pop() {
            if(index < 0) return;
            //4.出栈 -- 相当于删除栈顶元素 -- 栈顶赋值为 null
            arr[index--] = null;
        }

        public int top() {
            if (index < 0) return Integer.parseInt(null);
            //5.返回栈顶元素 -- 自动拆箱
            return arr[index];
        }

        public int getMin() {
            if (index < 0) return Integer.parseInt(null);

            //6.遍历数组寻找最小值
            int minus = arr[0]; //最小值
            for (int i=1; i<=index; i++){
                minus = arr[i] < minus ? arr[i] : minus;
            }
            return minus;
        }
    }

执行耗时：65 ms，击败了 7.35% 的Java用户
内存消耗：40.2 MB，击败了 55.30% 的Java用户
时间复杂度：O(n) -- 数组的遍历 O(n)，数组的扩容 O(n)
空间复杂度：O(n) -- 数组的内存空间 O(n)

四. Consider 思考更优解

改变算法思维！

思路：

• 每次获取最小值时，都需要重新 遍历 数组，效率很低
• 不难发现，每个元素在被压入栈顶的时候，栈的最小值都只有 两种状态 ：
  1.当前元素为最小值（状态一：某个新的数值）
  2.以前的最小值仍为最小值（状态二：原数值）
• 能否利用栈的特性，弹出栈顶元素的时候，将最小值的状态变化也一并弹出？

方法：

• 让每个元素都携带一个“快照”，记录此元素入栈后（这一时刻）栈的最小值。
• 当前栈的最小值 == 当前栈顶元素快照中的值
• 当栈顶元素被弹出，上个元素成为栈顶，上个快照被启用，最小值回滚

解法二：使用链表实现栈结构，栈的最小值由栈顶元素携带

• 数据结构：链表（链栈）
• 算法思维：状态机、快照、栈特性（LIFO）

五. Code 编码实现最优解

 class MinStack {

        //1.声明一个内部类 -- 链表节点
        private class Node{
            int val; //当前节点值
            int min; //最小值快照 -- 当前节点入栈后，栈的最小值

            Node next; //指针

            public Node(){}

            public Node(int val, int min, Node next){
                this.val = val;
                this.min = min;
                this.next = next;
            }
        }

        //2.声明一个链表头 -- 栈顶
        Node head;

        /**
         * initialize your data structure here.
         */
        public MinStack() {
            //3.初始化链栈
            head = null;
        }

        public void push(int x) {
            //4.节点入栈时，判断链表长度
            if (head == null) {
                head = new Node(x,x,null);
            } else {
                //5.每次入栈时，比较最小值，将此刻的最小值存入 new Node().min 中
                head = new Node(x,Math.min(x,head.min),head);
            }
        }

        public void pop() {
            //6.出栈时，直接弹出即可，最小值随之回滚
            if (head != null) head = head.next;
        }

        public int top() {
            //7.查栈顶
            return head != null ? head.val : Integer.parseInt(null);
        }

        public int getMin() {
            //8.查最小值 -- 其实就是查当前栈顶的最小值快照
            return head != null ? head.min : Integer.parseInt(null);
        }
    }

执行耗时：6 ms，击败了 96.02% 的Java用户
内存消耗：40.3 MB，击败了 36.21% 的Java用户
时间复杂度：O(1) -- 栈顶元素的直接查询 O(1)
空间复杂度：O(n) -- 链栈的内存空间 O(n)

六. Change 变形与延伸

=== 待续 ===