water fountain 会管用吗？ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>pets - 心有所宠

water fountain 会管用吗？

water fountain 会管用吗？# pets - 心有所宠

s*b2010-05-23 07:05

1 楼

Moving-window maximum.
Input: A long array A[], and a window width w
Output: An array B[],B[i] is the maximum value of from A[i] to A[i+w-1]
Requirement: find a good optimal to get B[i]
I can think of two solutions
First solution:
if(A[i] = !B[i-1]) B[i] = B[i-1]
else B[i] = max{A[i],...A[i+w-1]}
Second solution(this one is from one of my friend)
Use minHeap to store w number, each time when a new number A[i] enters,
age out the oldest one, and use O(logW) time to get max value of A[i-w+1]
to A[i]
Any good ideas or better solutions?

R*r2010-05-23 07:05

2 楼

请教大家：我的H1b今年7月1日过期，今天收到的renewal approval notice上面的有效
日期是7/20/12开始。这样的话会有问题么？对今后返签以及绿卡会有影响么？多谢多谢
！

a*m2010-05-23 07:05

3 楼

心里堵得慌。。
这个房子是看了几个月之后觉得各方面都不错的一个，准备自住几年。学区很好，环境
也还不错，位于一个很polular的community，property本身也算比较满意，觉得将来应
该会很好 resale。
房子上市3天就收到5个offer，其中两个all cash。我们不是出的最高价，但是很运气
我们得到了seller的偏爱，于是很顺利地被接受。当然房价并不算便宜，称不上deal。
可我们想既然喜欢也满意，seller能同意offer也可以了。
可是前两天才发现，隔壁city将在不久的将来修建一个大型stadium/entertainment
complex，是national级别的，狗狗地图了一下，大概距离这个房子才1mile多点不到
2miles。。。关键是这个房子的小区在一条主干道附近，（但房子本身不临街，在小区
内部弯弯绕绕的一条circle里）这条主干道上下连接几条
freeway，本来只是city的居民使用。如果stadium真的修成那只要有比赛应该就会有很
多车辆来，必定很堵塞，另外有噪音以及复杂的外来人员等等问题。目前还不知道什么
时候会动工修建。
我们

c*k2010-05-23 07:05

4 楼

黑子现在不爱喝水了，看到宠物店里面那种会自动流水的小盆，广告说会吸引猫猫喝水
，有人用过吗？

D*72010-05-23 07:05

5 楼

可以以你朋友的方案为基础再优化一下。
1) sort the cache used to store the w number
2) when a new number A[i] comes:
if (A[i] == A[i-w])
// nothing to do
else if (A[i] > A[i-w])
// 从后向前遍历cache，先是删除A[i-w]，然后不断的cache[j]=cache[j-1]，
直到将A[i]插入cache
else
// 从前向后遍历cache，先是删除A[i-w]，然后不断的cache[j]=cache[j+1]，
直到将A[i]插入cache

【在 s*****b 的大作中提到】

: Moving-window maximum.
: Input: A long array A[], and a window width w
: Output: An array B[],B[i] is the maximum value of from A[i] to A[i+w-1]
: Requirement: find a good optimal to get B[i]
: I can think of two solutions
: First solution:
: if(A[i] = !B[i-1]) B[i] = B[i-1]
: else B[i] = max{A[i],...A[i+w-1]}
: Second solution(this one is from one of my friend)
: Use minHeap to store w number, each time when a new number A[i] enters,

g*n2010-05-23 07:05

6 楼

理论上一天的gap也不该有。实际上20天gap没啥大不了的，放心吧。

w*62010-05-23 07:05

7 楼

建成以后，你能用么，比如去跑步，健身，如果能用，就是加分。
农村有national 的sports complex, 我认为是好事，除非是 metro里面的才有严重交
通和安全问题。

p*f2010-05-23 07:05

8 楼

管用。我家用第二个了。

i*e2010-05-23 07:05

9 楼

You said use minHeap, that's fine :)
But how to age out the oldest one? You have to search for the heap right?
The key to answering this problem is remove the leftmost element as
efficient as possible.
Hint: Hash table
Deng107:
You're doing a linear search in the heap. The worst case would happen such that your cache won't help at all. So you need O(w) to remove the leftmost element in each pass.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 s*****b 的大作中提到】

c*22010-05-23 07:05

10 楼

make sure your approval notice show a RD/ND that is before old I-94
expiration. If not, also safe keep your H1 renewal receipt notice showing
the receipt date.

x*y2010-05-23 07:05

11 楼

这个贴不是在华人上问过了嘛，看来LZ想多参考意见呀。

k*a2010-05-23 07:05

12 楼

Hash table can help remove the leftmost element, but how to make sure the
heap is sorted?

T*U2010-05-23 07:05

13 楼

这些地方经常会搞motel apartment，不是好事。

i*e2010-05-23 07:05

14 楼

The minHeap maintain the order when an element is being inserted. The insert
operation takes O(lg N) time complexity.
>> Hash table can help remove the leftmost element ...
Could you explain how? Many people know that the minHeap is the right data structure, but how hash table helps to accomplish removing the leftmost element in O(1) time is the heart of this problem.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

b*d2010-05-23 07:05

15 楼

50块钱一个停车位赚回来

k*a2010-05-23 07:05

16 楼

Maintain a hash table so that given the value of leftmost element, you can
know the position in minHeap

m*r2010-05-23 07:05

17 楼

My guess is there will be major traffic jam in 57/60 merge and Diamond Bar
will be a lot more noisy than it is now ...

i*e2010-05-23 07:05

18 楼

这明显不对啊
首先，在 minHeap 里只能 O(1) 索取排在第一位的元素。 minHeap 不是 array，不能
O(1) random access.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 k*****a 的大作中提到】

: Maintain a hash table so that given the value of leftmost element, you can
: know the position in minHeap

W*r2010-05-23 07:05

19 楼

IMO, local stadium cause traffic jam, noise, parking issue and crime rate.
Stadium attracts teenagers and commoners. They tend to get drunk after the
show or game.
for your reference:
http://www.arlingtontx.gov/cityhall/pdf/Stadium_Area_Crime_Analysis.pdf

i*e2010-05-23 07:05

20 楼

另外，要补充一下，这题的思路有一小部分跟一道经典题 "Finding the Minimum
Window in S which Contains All Elements from T" 很相似。
做了这题之后，你会发现 hash table 可以利用得如此巧妙.
强烈推荐参考 stormrage 兄给的精简答案：
http://www.mitbbs.com/article_t/JobHunting/31731763.html
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

n*a2010-05-23 07:05

21 楼

Diamond Bar?

h*32010-05-23 07:05

22 楼

想了半天也没想出2题的相似之处。。。。。
觉得还是用hash+heap,hash把 index of the array 影射为一个指针，指向这个结点在heap中的位置。每次就是调整heap,所以复杂读为O(n*logW).

【在 i**********e 的大作中提到】

: 另外，要补充一下，这题的思路有一小部分跟一道经典题 "Finding the Minimum
: Window in S which Contains All Elements from T" 很相似。
: 做了这题之后，你会发现 hash table 可以利用得如此巧妙.
: 强烈推荐参考 stormrage 兄给的精简答案：
: http://www.mitbbs.com/article_t/JobHunting/31731763.html
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com

c*e2010-05-23 07:05

23 楼

绝对太闹,不要了吧

【在 a**m 的大作中提到】

: 心里堵得慌。。
: 这个房子是看了几个月之后觉得各方面都不错的一个，准备自住几年。学区很好，环境
: 也还不错，位于一个很polular的community，property本身也算比较满意，觉得将来应
: 该会很好 resale。
: 房子上市3天就收到5个offer，其中两个all cash。我们不是出的最高价，但是很运气
: 我们得到了seller的偏爱，于是很顺利地被接受。当然房价并不算便宜，称不上deal。
: 可我们想既然喜欢也满意，seller能同意offer也可以了。
: 可是前两天才发现，隔壁city将在不久的将来修建一个大型stadium/entertainment
: complex，是national级别的，狗狗地图了一下，大概距离这个房子才1mile多点不到
: 2miles。。。关键是这个房子的小区在一条主干道附近，（但房子本身不临街，在小区

i*e2010-05-23 07:05

24 楼

你这方法我想了想，应该是不行的。
试想想，假设有重复的数字怎么处理呢？
[3, 5, 2], 5
hash[5] = pointer that point to node with value 5.
sliding window move to the right 1 step.
3, [5, 2, 5]
Now, you have two 5's. If you choose hash[5] to point to the first 5, which
will be deleted next, so now hash[5] points to nothing!
这问题最优解好像是 O(N)，大家再努力想想吧。
（以下的解法是利用 hash table 来数每一个数字出现的次数，不是最优解，复杂度为
O(N lg W)，W = sliding window 的长度
#include
#include
#include
#include
#include
using namespace std;
int main() {
freopen("data.txt", "r", stdin);
int n, w;
int* arr = new int[1000001];
int* outMax = new int[1000001];
priority_queue qMax;
hash_map h;
cin >> n >> w;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
outMax[0] = INT_MIN;
for (int i = 0; i < w; i++) {
qMax.push(arr[i]);
h[arr[i]]++;
if (arr[i] > outMax[0])
outMax[0] = arr[i];
}
for (int i = w; i < n; i++) {
qMax.push(arr[i]);
h[arr[i]]++;
h[arr[i-w]]--;
int topMax = qMax.top();
while (h[topMax] == 0) {
qMax.pop();
topMax = qMax.top();
}
outMax[i-w+1] = topMax;
}
for (int i = 0; i < n-w+1; i++) {
cout << outMax[i];
if (i != n-w) cout << " ";
}
cout << endl;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

点在heap中的位置。每次就是调整heap,所以复杂读为O(n*logW).

【在 h*********3 的大作中提到】

:
: 想了半天也没想出2题的相似之处。。。。。
: 觉得还是用hash+heap,hash把 index of the array 影射为一个指针，指向这个结点在heap中的位置。每次就是调整heap,所以复杂读为O(n*logW).

l*r2010-05-23 07:05

25 楼

its a big no no
Move on

b*c2010-05-23 07:05

26 楼

This is also the interview question of Google.
Please check the following link for perfect solution:
http://www.mitbbs.com/article_t1/JobHunting/31728173_0_1.html

a*m2010-05-23 07:05

27 楼

WALNUT。。。snow creek靠近valley:(

【在 n*****a 的大作中提到】

: Diamond Bar?

H*72010-05-23 07:05

28 楼

h[arr[i]]++;
这一句什么意思？
C++不是很熟。请指点一下

which

【在 i**********e 的大作中提到】

: 你这方法我想了想，应该是不行的。
: 试想想，假设有重复的数字怎么处理呢？
: [3, 5, 2], 5
: hash[5] = pointer that point to node with value 5.
: sliding window move to the right 1 step.
: 3, [5, 2, 5]
: Now, you have two 5's. If you choose hash[5] to point to the first 5, which
: will be deleted next, so now hash[5] points to nothing!
: 这问题最优解好像是 O(N)，大家再努力想想吧。
: （以下的解法是利用 hash table 来数每一个数字出现的次数，不是最优解，复杂度为

a*m2010-05-23 07:05

29 楼

估计这样的stadium不对public开放的吧我猜。。

【在 w********6 的大作中提到】

: 建成以后，你能用么，比如去跑步，健身，如果能用，就是加分。
: 农村有national 的sports complex, 我认为是好事，除非是 metro里面的才有严重交
: 通和安全问题。

H*72010-05-23 07:05

30 楼

h[arr[i]]++;
h[arr[i-w]]--;
C++里的HASHMAP我不熟悉。这是在做什么？谢谢

a*m2010-05-23 07:05

31 楼

哎真是闹心。。

the

【在 W*****r 的大作中提到】

: IMO, local stadium cause traffic jam, noise, parking issue and crime rate.
: Stadium attracts teenagers and commoners. They tend to get drunk after the
: show or game.
: for your reference:
: http://www.arlingtontx.gov/cityhall/pdf/Stadium_Area_Crime_Analysis.pdf

k*a2010-05-23 07:05

32 楼

No hash table needed, a linked list can solve that, to map index of window
to index of minHeap, notice minHeap can be stored in an array. So for each
element, the time to maintain the linked list is O(1), the time to add/
delete in minHeap is O(1), the time to maintain a minHeap is between O(1) to
O(lg k).
Based on these, on average, it is O(n), in the worst case (removing root of
minHeap each time in case an sorted vector), it is O(n lg k)

which

【在 i**********e 的大作中提到】

p*w2010-05-23 07:05

33 楼

修个 rooftop 的观景台，收费。

【在 a**m 的大作中提到】

h*32010-05-23 07:05

34 楼

which
我是说hash index, 不是hash value, 你的例子里面，第一个5的index是2，第2个5
的index是5，index不会重复。

【在 i**********e 的大作中提到】

q*22010-05-23 07:05

35 楼

搂住多大岁数了？这问题不值得跪。。起来吧。。

k*a2010-05-23 07:05

36 楼

这个跟我最开始的思路一样，握手 . 但是不用hash table做mapping，linked
list就可以O（1）把 index of the array 影射为一个指针，hash反而复杂。

点在heap中的位置。每次就是调整heap,所以复杂读为O(n*logW).

【在 h*********3 的大作中提到】

:
: which
: 我是说hash index, 不是hash value, 你的例子里面，第一个5的index是2，第2个5
: 的index是5，index不会重复。

s*y2010-05-23 07:05

37 楼

Exactly. Why people will get down on their knees so easily? Stand up as a
man if you are a man.

【在 q**2 的大作中提到】

: 搂住多大岁数了？这问题不值得跪。。起来吧。。

i*e2010-05-23 07:05

38 楼

Thanks for the link.
According to AprilFlower:
>> 永远是从尾插入的，只要O(1)的。
如果要插入的数比当前尾部数大，要删除前面的数直到遇到比当前数大的再插入，链表
maintain的是一个递减的序列，并不是整个window的大小，也就是每个数最多插入/删
除一次，所以整个的复杂度是O(n)。。
I think I coded the solution and submitted here at POJ online judge:
http://poj.org/problem?id=2823
I uploaded a copy of my code here (Sorry it's a bit messy and there's part
that I copy and paste here and there :( ) The basic idea is using a doubly-linked list and maintain the linked list by only doing insert/remove operation at the two ends of the list.
http://www.ideone.com/16Xfp
However, I get Time limit exceeded... Any suggestion? Did I implement it
wrongly?
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 b*****c 的大作中提到】

: This is also the interview question of Google.
: Please check the following link for perfect solution:
: http://www.mitbbs.com/article_t1/JobHunting/31728173_0_1.html

h*i2010-05-23 07:05

39 楼

snow creek的房子怎么说也要70万以上。

【在 a**m 的大作中提到】

: WALNUT。。。snow creek靠近valley:(

i*e2010-05-23 07:05

40 楼

这代表 hash table 里的值加一个或者减一。
一开始的初始值是 0.
h[0]++ --> increment h[0] by 1, now h[0] = 1
h[3]-- --> decrement h[3] by 1, now h[3] = -1
h[0]++ --> increment h[0] by 1, now h[0] = 2
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 H******7 的大作中提到】

: h[arr[i]]++;
: h[arr[i-w]]--;
: C++里的HASHMAP我不熟悉。这是在做什么？谢谢

H*H2010-05-23 07:05

41 楼

1 mile多的距离有点太近了。
不过一般体育场也不会天天用，每年重大活动用两天也不是什么大问题啊。

i*e2010-05-23 07:05

42 楼

kongbua,
>> Based on these, on average, it is O(n), in the worst case (removing root
of minHeap each time in case an sorted vector), it is O(n lg k)
I don't think this statement is correct. Your average is still O(n lg k). Based on your statement:
The time to maintain a minHeap is between O(1) to O(lg k). This does not prove that the average case is O(N).
>> 这个跟我最开始的思路一样，握手 . 但是不用hash table做mapping，linked
list就可以O（1）把 index of the array 影射为一个指针，hash反而复杂。
Sorry I misunderstood. Could you please paste your code (or pseudocode)? I
don't quite understand how you can use linked list to map to an element's
index. (Is it the node store the data (a pointer) that points to an element?)
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

to
of

【在 k*****a 的大作中提到】

: No hash table needed, a linked list can solve that, to map index of window
: to index of minHeap, notice minHeap can be stored in an array. So for each
: element, the time to maintain the linked list is O(1), the time to add/
: delete in minHeap is O(1), the time to maintain a minHeap is between O(1) to
: O(lg k).
: Based on these, on average, it is O(n), in the worst case (removing root of
: minHeap each time in case an sorted vector), it is O(n lg k)
:
: which

a*m2010-05-23 07:05

43 楼

收到，改了！

【在 q**2 的大作中提到】

: 搂住多大岁数了？这问题不值得跪。。起来吧。。

P*l2010-05-23 07:05

44 楼

O(n) algorithm:
public Integer[] getMaxInSlideWindow(Integer[] A, Integer w) {
// invalid input
if (A == null || w <= 0 || A.length - w + 1 <= 0)
return null;
Integer[] B = new Integer[A.length - w + 1];
// auxiliary queue that is sorted in descending order
List q = new LinkedList();
for (int i = 0; i < A.length; i++) {
// enqueue. Remove those smaller values
int data = A[i];
while (!q.isEmpty() && q.get(q.size() - 1) < data) {
q.remove(q.size() - 1);
}
q.add(data);
if (i < w - 1)
continue;
// dequeue. If the current number is the maximum. Also remove it
// from the queue
Integer max = q.get(0);
B[i - w + 1] = max;
if (A[i - w + 1] == max)
q.remove(0);
}
return B;
}

a*m2010-05-23 07:05

45 楼

本来是不错的，就是担心修了之后造成整个区跌价。。以后不好resale.
房子本身真的喜欢，所以好纠结。

【在 h***i 的大作中提到】

: snow creek的房子怎么说也要70万以上。

P*l2010-05-23 07:05

46 楼

呃。。。
崔浩有诗在上头。。

g*72010-05-23 07:05

47 楼

Why would the seller prefer your offer over all cash?

【在 a**m 的大作中提到】

i*e2010-05-23 07:05

48 楼

Nice solution.
My algorithm is the same as yours, although your code is much more elegant,
good job!
I submitted your code (with some modification) to here, it still gives me
Time Limit Exceeded.
Could you try to submit your code here? (You would need to output the
minimum sliding window value as well).
http://poj.org/problem?id=2823
This solution which uses the simple idea of heap + linear search in heap
passes the judge.
http://blogold.chinaunix.net/u3/105033/showart_2209043.html
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 P********l 的大作中提到】

: O(n) algorithm:
: public Integer[] getMaxInSlideWindow(Integer[] A, Integer w) {
: // invalid input
: if (A == null || w <= 0 || A.length - w + 1 <= 0)
: return null;
: Integer[] B = new Integer[A.length - w + 1];
: // auxiliary queue that is sorted in descending order
: List q = new LinkedList();
: for (int i = 0; i < A.length; i++) {
: // enqueue. Remove those smaller values

a*m2010-05-23 07:05

49 楼

我们是list出来之后第一个去看房的；最近父母也从中国过来一起看房，seller觉得很诚恳；跟seller聊天，seller的经历跟我们很相似因此很投缘，当天晚上就跟agent说要卖给我们，当时seller都不知道我们的offer也不知道别人的offer。当然最重要的是seller不着急搬家不需要cash，他们的新家还在装修中，他们给的counter offer就是可能close之后需要租一个月，付相应的租金给我们。我们同意

【在 g******7 的大作中提到】

: Why would the seller prefer your offer over all cash?

i*e2010-05-23 07:05

50 楼

Sorry, I've deleted some of my previous posts to avoid confusion. kongbua is right, this problem actually does not require hash table.
A single priority queue is sufficient. Instead of pushing the array's value
into the queue, push the array's index into the queue. Apply the queue's
ordering that is based on the array's value, not its index. The average
complexity of this method is k*(N-W) lg W. Is this O(N) or O(N lg W)? I
think this is O(N), since W <= N, lg W is pretty significant compared to N,
in addition W is a constant. (I am not 100% sure though)
The other method is to maintain a single linked list. This is O(N) because
there are total maximum of 2*N insert/remove operations onto the list at
most.
Which method is faster? In theory, it seemed that the second method is
faster. In real life however, I guess this is still debatable, because
depending on the constant factor, the queue method might be faster.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

m*a2010-05-23 07:05

51 楼

你不会是买在我后花园对着的那个刚上市几天就pending的房子吧?哈哈,如果是,就太巧
了.根据你说的,应该就是那个了,刚上市几天就pending了.价钱不算太高的.

P*l2010-05-23 07:05

52 楼

The code is accepted. But note that it consumes 40M memory + 36.5s. I
don't know what funky test data they used. Somehow the robot judge does
not accept the "package", I get "run time error" 9 times.
8111807 puttyshell 2823 Accepted 40168K 36454MS Java
2357B 2011-01-23 14:34:47

a*m2010-05-23 07:05

53 楼

啊呵呵，不会这么巧吧。。那您说说意见吧。你家院子地势应该更高对不对？
这个区我真喜欢，居民对这个未来的体育场啥感觉啊？您觉得会影响小区今后的房价么？
我看的这个不算高价，也不是deal，里面没有upgrade,还得花钱装。。

【在 m*****a 的大作中提到】

: 你不会是买在我后花园对着的那个刚上市几天就pending的房子吧?哈哈,如果是,就太巧
: 了.根据你说的,应该就是那个了,刚上市几天就pending了.价钱不算太高的.

c*n2010-05-23 07:05

54 楼

这个方法对这个题是最优，但是heap-based solution 实际上解决了另一个更难的问题：
求moving window of width W 里面最大的K 个数。

【在 P********l 的大作中提到】

m*a2010-05-23 07:05

55 楼

我当时买的时候也知道要建这个体育场,可是我的确喜欢这个区,而且感觉距离是近,可
是毕竟snow creek是好区,city 总不会让他们真的向这边扩张的,而且建这种体育场也
不是一天两天的事情了,我同事住在Diamond Bar,他说电台里面说这个体育场的项目要
延后.
再说,建起来了,也不一定是坏事的,我当初住arcadia,有mall,有跑马场,还有一个很好
的down town,这些都成为了吸引别人来居住的条件, 所以房价也结节上升了.
这个区是好区,很多人喜欢的,而且住下去了,我感觉是不错,除了我太太抱怨生活不是太
便利以外(那是跟Arcadia比),环境很好,而且很安静,学区也很好.所以房价基本没有怎
么跌.

l*l2010-05-23 07:05

56 楼

This sounds like a simple problem, O(N) time, O(1) space.
First calculate the sum of the left-most window. Then slide the window from
left to right step by step, update current sum by subtracting the one just
removed and adding the one just added. Update the current maximum sum and its start index. After one scan, copy the maximun window to the output.

a*m2010-05-23 07:05

57 楼

哈，太巧了，我们现在就住Arcadia。。。我就是觉着这个区真不错。
谢谢你啊

【在 m*****a 的大作中提到】

: 我当时买的时候也知道要建这个体育场,可是我的确喜欢这个区,而且感觉距离是近,可
: 是毕竟snow creek是好区,city 总不会让他们真的向这边扩张的,而且建这种体育场也
: 不是一天两天的事情了,我同事住在Diamond Bar,他说电台里面说这个体育场的项目要
: 延后.
: 再说,建起来了,也不一定是坏事的,我当初住arcadia,有mall,有跑马场,还有一个很好
: 的down town,这些都成为了吸引别人来居住的条件, 所以房价也结节上升了.
: 这个区是好区,很多人喜欢的,而且住下去了,我感觉是不错,除了我太太抱怨生活不是太
: 便利以外(那是跟Arcadia比),环境很好,而且很安静,学区也很好.所以房价基本没有怎
: 么跌.

d*22010-05-23 07:05

58 楼

shouldn't this be simpler by just using an array based stack, so that you
don't have to maintain link node and allocate new memory? A c++ version:
void MovingWindowMax(int* a, int n, int w, int* b)
{
Stack* stack = new Stack(w); //an array implementation of stack.
max capacity is w at any time.
for(int i=0; i{
while(!stack.Empty() && stack.Peek() < a[i])
stack.Pop();
stack.Push();
if(icontinue;
b[i-w+1] = stack.Peek();
if(a[i-w+1] == b[i-w+1])
stack.Pop();
}
}

m*a2010-05-23 07:05

59 楼

哇,猿粪哪,咱们居然以前就住一个城市,将来也许也住一个城市啊.

i*e2010-05-23 07:05

60 楼

Try this example:
n = 3, w = 2.
a = [5 4 3]
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

.

【在 d****2 的大作中提到】

: shouldn't this be simpler by just using an array based stack, so that you
: don't have to maintain link node and allocate new memory? A c++ version:
: void MovingWindowMax(int* a, int n, int w, int* b)
: {
: Stack* stack = new Stack(w); //an array implementation of stack.
: max capacity is w at any time.
: for(int i=0; i: {
: while(!stack.Empty() && stack.Peek() < a[i])
: stack.Pop();

a*m2010-05-23 07:05

61 楼

还真是猿粪呐。。
Arcadia暂时买不起满意的，Diamond bar更远，只有walnut合适了。

【在 m*****a 的大作中提到】

: 哇,猿粪哪,咱们居然以前就住一个城市,将来也许也住一个城市啊.