r****4
发帖数: 168 | 1 我在做leetcode，这个是要求所有push， pop， top， getMin， 时间消耗都是常量。
这个是我的code，
class MinStack {
List stack = new ArrayList();
List mins = new ArrayList();
int min = 0;
public void push(int x) {
stack.add(x);
if(mins.isEmpty() || x < min) {
mins.add(stack.size());
min = x;
}
}
public void pop() {
Integer temp = mins.get(mins.size() - 1 );
if(temp == stack.size()) {
mins.remove(temp);
}
stack.remove(stack.get(stack.size() - 1));
}
public int top() {
int topEle = stack.get(stack.size() - 1);
return topEle;
}
public int getMin() {
int topEle = mins.get(mins.size() - 1 );
return stack.get(topEle - 1);
}
}
运行后几万个递增的push到minstack 后，报time limit exceed problem。我没懂我的
这个为啥会超时？ 我的push操作在时间上是常量啊。
找了一个答案是用Node， 这个node里放最小值和当前值，还有前一个Node的地址。这
个答案的push是每一个新数据进来，先new 一个node，记录前一个Node地址。
我不知道为什么用Node 会没有超时的问题。
谁能解答下吗？ |
b******y
发帖数: 9224 | |
F****n
发帖数: 3271 | 3 ArrayList uses an underlying array, and if it length is exceeded a new array
will be created and data copied, which takes O(N) time.
For tests and interview, you should use LinkedList.
For real world projects, I recommend use new ArrayList(N) in
practice, where N is the estimated maximal number of elements in your stack.
【在 r****4 的大作中提到】
: 我在做leetcode，这个是要求所有push， pop， top， getMin， 时间消耗都是常量。
: 这个是我的code，
: class MinStack {
: List stack = new ArrayList();
: List mins = new ArrayList();
: int min = 0;
: public void push(int x) {
:
: stack.add(x);
: if(mins.isEmpty() || x < min) {
|
g**e
发帖数: 6127 | 4 In real world linked list performance is worse than array list in almost all
use cases.
array
stack.
量。
【在 F****n 的大作中提到】
: ArrayList uses an underlying array, and if it length is exceeded a new array
: will be created and data copied, which takes O(N) time.
: For tests and interview, you should use LinkedList.
: For real world projects, I recommend use new ArrayList(N) in
: practice, where N is the estimated maximal number of elements in your stack.
|
F****n
发帖数: 3271 | 5 That's not true. There are cases where you need a million of objects with
small but variant-sized lists. In such cases you should use LinkedList
because the memory will be fragmented anyway.
all
【在 g**e 的大作中提到】
: In real world linked list performance is worse than array list in almost all
: use cases.
:
: array
: stack.
: 量。
|
g*****g
发帖数: 34805 | 6 Of course there are cases you want to use linklist, such as a queue.
all
【在 g**e 的大作中提到】
: In real world linked list performance is worse than array list in almost all
: use cases.
:
: array
: stack.
: 量。
|
