丰县徐州网站开发,梁山网站开发,南宁百度关键词推广,专业门户网站开发公司155.最小栈
设计一个支持 push #xff0c;pop #xff0c;top 操作#xff0c;并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元…155.最小栈
设计一个支持 push pop top 操作并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin() 获取堆栈中的最小元素 思路
根据栈的先进先出的特性对于栈来说如果一个元素a在入栈时栈里有其他元素b,c,d无论这个栈在之后经历了什么操作只要a在栈中b,c,d就一定在栈中因为a被弹出之前b,c,d不会被弹出
因此在操作过程中的任意一个时刻只要栈顶的元素是a那么我们就可以确定栈里面现在的元素一定是a,b,c,d
可以在每个元素a入栈时把当前栈的最小值m存储起来在这之后无论何时如果栈顶元素是a,就可以直接返回存储的最小值m
算法
只需要设计一个数据结构使得每个元素a与相应的最小值m时刻保持一一对应因此我们可以使用一个辅助栈与元素栈同步插入与删除每次比较栈顶元素与插入元素的大小保证每次栈顶元素都是最小值该辅助栈主要是用于存储与每个元素对应的最小值
当一个元素要入栈时取当前辅助栈的栈顶存储的最小值与当前元素比较得出最小值将这个最小值插入辅助栈中当一个元素要出栈时把辅助栈的栈顶元素也一并弹出在任意一个时刻栈内元素的最小值就存储在辅助栈的栈顶元素中 class MinStack {DequeInteger xStack;DequeInteger minStack;public MinStack() {xStack new LinkedListInteger();minStack new LinkedListInteger();minStack.push(Integer.MAX_VALUE);}public void push(int val) {xStack.push(val);minStack.push(Math.min(minStack.peek(),val)); //取当前辅助栈的栈顶存储的最小值}public void pop() {xStack.pop();minStack.pop();}public int top() {return xStack.peek();}public int getMin() {return minStack.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj new MinStack();* obj.push(val);* obj.pop();* int param_3 obj.top();* int param_4 obj.getMin();*/
