javascript - 顶部方法的最小堆栈解决方案错误?
问题描述
我的输入输出
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
是
[null,null,null,null,-3,null,-3,-2]
而预期是
[null,null,null,null,-3,null,0,-2]
我希望该"top"
方法是我的问题所在,但我无法弄清楚我做错了什么。有人可以为我指出吗?我正在使用两个堆栈来解决问题。一个用于推送输入的堆栈和一个通过将其值与第一个堆栈的值进行比较来将输入推入的 minStack。
/**
* initialize your data structure here.
*/
let MinStack = function() {
this.stack = new Stack();
this.minStack = new Stack();
};
/**
* @param {number} x
* @return {void}
*/
MinStack.prototype.push = function(x) {
this.stack.push(x);
if (this.minStack.size === 0) {
this.minStack.push(x);
} else if (x <= this.minStack.peek()) {
this.minStack.push(x);
}
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
let popped = this.stack.peek();
if (popped === this.minStack.peek()) {
this.minStack.pop()
}
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.stack.peek();
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
return this.minStack.peek();
};
class Stack {
constructor() {
this.storage = {};
this.size = 0;
}
push(val) {
this.storage[this.size] = val;
this.size++;
}
pop() {
let top = this.storage[this.size - 1];
delete this.storage[this.size - 1];
this.size--;
return top;
}
peek() {
return this.storage[this.size - 1];
}
getSize() {
return this.size;
}
empty() {
return this.size === 0;
}
}
解决方案
好问题!
不确定您的错误,我们可以只使用 JavaScript 数组来解决这个问题。这会顺利通过的:
var MinStack = function() {
this.stack = [];
};
MinStack.prototype.push = function(x) {
this.stack.push({
value: x,
min: this.stack.length === 0 ? x : Math.min(x, this.getMin()),
});
};
MinStack.prototype.pop = function() {
this.stack.pop();
};
MinStack.prototype.top = function() {
return this.stack[this.stack.length - 1].value;
};
MinStack.prototype.getMin = function() {
return this.stack[this.stack.length - 1].min;
};
如果您想使用自己的Stack()
,请在此处将其插入上述代码:
this.stack = [];
它应该可以正常工作。为此,您将不得不编写一个min()
方法,我想它会像:
class MyOwnMinStack {
constructor() {
this.storage = {};
this.size = 0;
this.currMin = null
}
push(val) {
this.storage[this.size] = val;
this.size++;
}
pop() {
let top = this.storage[this.size - 1];
delete this.storage[this.size - 1];
this.size--;
return top;
}
peek() {
return this.storage[this.size - 1];
}
getSize() {
return this.size;
}
empty() {
return this.size === 0;
}
min() {
// To do
return this.currMin;
}
}
每次我们会push()
或pop()
时,我们都会跟踪this.currMin
,这样O(1)
一旦min()
被调用,我们就会以恒定的时间复杂度返回它。
在这里,我将复制一些其他方法来解决其他语言的问题,可能会帮助您解决问题。例如,这个c++方法使用两个堆栈:
class MinStack {
private:
stack<int> stack_one;
stack<int> stack_two;
public:
void push(int x) {
stack_one.push(x);
if (stack_two.empty() || x <= getMin())
stack_two.push(x);
}
void pop() {
if (stack_one.top() == getMin())
stack_two.pop();
stack_one.pop();
}
int top() {
return stack_one.top();
}
int getMin() {
return stack_two.top();
}
};
Python
class MinStack:
def __init__(self):
self.stack = [(float('inf'), float('inf'))]
def push(self, x):
self.stack.append((x, min(x, self.stack[-1][1])))
def pop(self):
if len(self.stack) > 1:
self.stack.pop()
def top(self):
if len(self.stack) > 1:
return self.stack[-1][0]
return
def getMin(self):
if len(self.stack) > 1:
return self.stack[-1][1]
return
爪哇
class MinStack {
int min = Integer.MAX_VALUE;
Stack<Integer> stack = new Stack<Integer>();
public void push(int x) {
if (x <= min) {
stack.push(min);
min = x;
}
stack.push(x);
}
public void pop() {
if (stack.pop() == min)
min = stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return min;
}
}
参考
推荐阅读
- android - 想要在 Android 应用程序的视图中从图像资源中使用 draw 方法创建对象类
- python - Python GUI 的启动画面
- javascript - 具有默认值的表单上的 SessionStorage
- c - 如何直接从序数 12 调用 SHCreateMemStream()
- c++ - 使用 mingW g++ 解决 Visual Studio Code 中的“致命错误:GLFW/glfw3.h: No such file or directory”
- electron - 在 electron-builder 中首次安装后使用一键安装
- prolog - 从两个列表中减去元素 | 序言
- python - 与 if 语句混淆
- vb.net - 如何使用 vb.net 连接到 Clipper (E5) DBF 文件(带有 SMT)
- python - 如何修复更新库存项目数量?