最小栈问题

题目：如何实现一个栈，既存在基本的push pop操作，又可以有getMin操作，注：元素均是int型

原始方法：维持一个变量，使之保存入栈的最小值，当第一个最小值出去后，遍历剩下的栈元素并更新最小值变量，这种算法pop的时间复杂度是O(n)，其他操作的时间复杂度都是O(1)，空间复杂度是O(1)；

改进1：如果可以申请一个连续内存来存放不同阶段的最小值，那么就不需要每次遍历了，典型的空间换时间。最方便的是申请一个栈min，每次push的时候，如果是比当下最小值还要小，则也push进min栈，否则min栈重复push当前最小值，也就是说保持两个栈元素数量一致，这样每次pop的时候，min栈顶元素就是当前的最小值。时间复杂度为O(1)，空间复杂度为O(n)

import java.util.ArrayList;
import java.util.List;
 
public class MinStack {
 
    private List<Integer> data = new ArrayList<Integer>();
    private List<Integer> mins = new ArrayList<Integer>();
 
    public void push(int num) {
        data.add(num);
        if(mins.size() == 0) {
            // 初始化mins
            mins.add(num);
        } else {
            // 辅助栈mins每次push当时最小值
            int min = getMin();
            if (num >= min) {
                mins.add(min);
            } else {
                mins.add(num);
            }
        }
    }
 
    public int pop() {
        // 栈空，异常，返回-1
        if(data.size() == 0) {
            return -1;
        }
        // pop时两栈同步pop
        mins.remove(mins.size() - 1);
        return data.remove(data.size() - 1);
    }
 
    public int getMin() {
        // 栈空，异常，返回-1
        if(mins.size() == 0) {
            return -1;
        }
        // 返回mins栈顶元素
        return mins.get(mins.size() - 1);
    }
 
}

该进2：我们发现上面的算法存在大量的重复元素，因此还有可优化空间。如果新push的值不小于最小值，在min栈里我们可以不重复push最小值，在pop的时候，我们先判断栈顶元素与min栈顶元素是否相同，如果相同min栈一同pop，否则min栈不动。当然，如果新push的元素大小与最小值相同，也要入min栈，这样才能保证数据正确性。

改进3：我们发现上面的算法还是会存在重复元素，也就是多个相同最小值入栈的时候。那么如何改进呢？用索引！在min栈中存储第一次出现最小值的索引，这样当重复出现最小值的时候无需重复存入，pop的时候只需要判断最小值索引还在不在即可，当索引pop的时候，min栈也随之pop，否则min栈不用动。

import java.util.ArrayList;
import java.util.List;
 
public class MinStack {
 
    private List<Integer> data = new ArrayList<Integer>();
    private List<Integer> mins = new ArrayList<Integer>();
 
    public void push(int num) throws Exception {
        data.add(num);
        if(mins.size() == 0) {
            // 初始化mins
            mins.add(0);
        } else {
            // 辅助栈mins push最小值的索引
            int min = getMin();
            if (num < min) {
                mins.add(data.size() - 1);
            }
        }
    }
 
    public int pop() throws Exception {
        // 栈空，抛出异常
        if(data.size() == 0) {
            throw new Exception("栈为空");
        }
        // pop时先获取索引
        int popIndex = data.size() - 1;
        // 获取mins栈顶元素，它是最小值索引
        int minIndex = mins.get(mins.size() - 1);
        // 如果pop出去的索引就是最小值索引，mins才出栈
        if(popIndex == minIndex) {
            mins.remove(mins.size() - 1);
        }
        return data.remove(data.size() - 1);
    }
 
    public int getMin() throws Exception {
        // 栈空，抛出异常
        if(data.size() == 0) {
            throw new Exception("栈为空");
        }
        // 获取mins栈顶元素，它是最小值索引
        int minIndex = mins.get(mins.size() - 1);
        return data.get(minIndex);
    }
 
}

最小栈问题

推荐阅读