前置

  • 数据结构—栈与队列
  • 算法题栈与队列
  • 编程语言: 尽管采用的Java,但避免了Java的容器特性, 读者应该很容易翻译成自己的语言。

题目

设计一个支持入栈、出栈、顶栈以及在常数时间内检索最小元素的堆栈。
这个栈需要支持常规栈的操作, 并且还能支持当前栈中的最小元素操作getMin方法。
getMin方法总是返回当前栈中的最小值。

力扣----最小栈

  • 力扣提供的接口
class MinStack {

    public MinStack() {

    }
    
    public void push(int val) {

    }
    
    public void pop() {

    }
    
    public int top() {

    }
    
    public int getMin() {

    }
}

解决方法

  1. 设计一个常规栈stackData正常压栈弹栈, 另外设计一个栈stackMin维护常规栈的最小值。

本题只需要想好压入逻辑就非常简单
假设压入数据为val

  • 若两个栈都为空, 则同步压入。
  • 若不为空, 那么讨论val与stackMin栈顶元素的大小关系。因为stackMin维护的是最小值, 那么val<=,则stackMin压入val,否则,stackMin重复压入自身当前的堆顶元素。
  • stackData全程进行常规压入操作。
  • 由于两个栈都同时进行压入元素,不过对于stackMin要讨论压入的元素, 可以用一个size字段维护两个栈的大小

弹出逻辑
size--即可,两个栈的逻辑都视为弹出元素

public class MinStack {
	//题目所给的最大压入压出操作量, 假设全部压栈至多MAX
	public static int MAX = 30001;
	public int[] stackData = new int[MAX];
	public int[] stackMin = new int[MAX];
	public int size;//维护两个栈的长度, 因为是同步压入两个栈长度相同。
	public MinStack() {
		
	}

	public void push(int val) {
		if(size==0) {
			stackMin[size] = val;
		}
		else if(val <= stackMin[size-1]) {
			stackMin[size]=val;
		}
		else {
			stackMin[size] = stackMin[size-1];
		}
		stackData[size++] = val;
	}
	//常规栈操作
	public void pop() {
		size--;
	}
	//常规栈操作
	public int top() {
		return stackData[size-1];
	}
	//获取最小值
	public int getMin() {
		return stackMin[size-1];
	}	
}

100%优化环节

上面的栈是手动写的数组, 在算法篇---栈与队列基础说明了, 不过时间复杂度还是慢啊。
如果先前采用java内置栈的话, 效率肯定不如数组。
既然是做算法题, 反正也是单线程, 直接开静态数组。
也不要每次开30001大小的数组, 实测可以开更小的数组, 足以应付测试用例。
顺便优化以下push方法的逻辑。

public class MinStack {
	//题目所给的最大压入压出操作量, 假设全部压栈至多MAX
	public static int MAX = 7501;//实测7501足够了
	//减少每次测数据的开销, 直接空间复用
	public static int[] stackData = new int[MAX];
	public static int[] stackMin = new int[MAX];
	public static int size;//维护两个栈的长度, 因为是同步压入两个栈长度相同。
	public MinStack() {
		size = 0;//这里需要重置size。
	}

	public void push(int val) {
	//||优化
		if(size==0 || val <= stackMin[size-1]) {
			stackMin[size] = val;
		}
		else {
			stackMin[size] = stackMin[size-1];
		}
		stackData[size++] = val;
	}
	//常规栈操作
	public void pop() {
		size--;
	}
	//常规栈操作
	public int top() {
		return stackData[size-1];
	}
	//获取最小值
	public int getMin() {
		return stackMin[size-1];
	}	
}

结果: 击败100%的人。
在这里插入图片描述

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部