网站的建设思想,网站建设用款,百度网盘搜索引擎网站,手机网站页面文字做多大力扣716#xff0c;设计一个最大栈数据结构#xff0c;既支持栈操作#xff0c;又支持查找栈中最大元素。 分析#xff1a; 在最大栈的问题上#xff0c;除了实现普通栈拥有的方法pop、push、top外#xff0c;还需要实现getMax方法来找到当前栈里的最大值。为了在最短事件…力扣716设计一个最大栈数据结构既支持栈操作又支持查找栈中最大元素。 分析 在最大栈的问题上除了实现普通栈拥有的方法pop、push、top外还需要实现getMax方法来找到当前栈里的最大值。为了在最短事件内获得栈中的最大值就不应该在执行getMax()方法时再去计算最小值最好应该在push或者pop的过程中就应该计算好当前栈中的最大值。还应有popMax()检索并删除栈中最大值并返回该值。 思路基于栈后进先出的特点那么在将一个数a压入栈中时如果栈里已经存在b,c,d那么无论这个栈之后执行什么操作如果a在栈中b,c,d就一定在栈中因为在a被弹出之前b,c,d不会被弹出在操作过程中的任意一个时刻只要a在栈顶那么栈里的元素就一定是a,b,c,d。既然如此我们就可以在每个新元素a入栈时把当前栈中的最大值maxValue存储到另外一个辅助栈中这样在后面的操作过程中只要栈顶元素为a我们就可以用getMax()直接返回当前栈中最大值。在将栈顶元素pop时我们同步将辅助栈中栈顶元素弹出这样就可以保证只要辅助栈不为空辅助栈里的栈顶元素始终都是当前栈的最大值。 将最大值存入辅助栈的算法步骤如下
当一个元素要入栈时我们去当前辅助栈的栈顶的最大值与当前元素进行比较得出最大值后将这个最大值压入辅助栈中。当一个元素要出栈时我们把辅助栈的栈顶元素同步弹出。
删除栈里的最大值的算法步骤如下
创建一个缓冲栈将原栈栈顶元素依次与辅助栈栈顶元素比较如果小于辅助栈栈顶元素就pop原栈顶元素并将其压入缓冲栈中保存如果等于辅助栈栈顶元素就执行pop操作同时弹出辅助栈栈顶元素。再将缓冲栈里的元素push回原栈并返回最大值。
代码如下
let MaxStack function() {this.topIndex -1;this.originStack [];this.maxValueStack [];
}/*** param {number} val* return {void}* */
MaxStack.prototype.push(val) {this.originStack.push(val);let maxValue (this.maxValueStack.length 0 ? val : this.maxValueStack.at(this.topIndex))this.maxValueStack.push(Math.max(maxValue, val);
}/*** return {number}* */
MaxStack.prototype.pop() {this.maxValueStack.pop();return this.originStack.pop();
}/*** return {number}* */
MaxStack.prototype.top() {return this.originStack.at(topIndex);
}/*** return {number}* */
MaxStack.prototype.peekMax() {return this.maxValueStack.at(this.topIndex);
}/*** return {number}* */
MaxStack.prototype.popMax() {let maxValue peekMax();const buffer [];while (top() ! maxValue) buffer.push(pop());pop();while (buffer.length ! 0) {push(buffer.pop());}return maxValue;
}
