最小栈问题

题目:如何实现一个栈,既存在基本的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);
    }
 
}

 

上一篇:hdu 4786 Fibonacci Tree


下一篇: