r***6
发帖数: 15 | 1 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
大值。
例如，
有数组 2，3，4，2，6，7，8，2，4，1，2，3
k = 3
输出
4，4，6，7，8，8，8，4，4，4
有什么好一点的解法吗。 |
b***e
发帖数: 15201 | 2 use heap?
【在 r***6 的大作中提到】
: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。
|
n**4
发帖数: 719 | 3 use a queue
keep the biggest value at the head of the queue |
P*A
发帖数: 189 | 4 Maintain a Binary Search Tree,
with a pointer to the max node,
Every time you insert a new element, update the pointer if necessary.
【在 r***6 的大作中提到】
: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。
|
g**********y
发帖数: 14569 | 5 public int[] getWindowMax(int[] a, int w) {
int[] b = new int[a.length - w + 1];
ArrayDeque q = new ArrayDeque();
for (int i=0; i
while (!q.isEmpty() && a[q.peekLast()]<=a[i]) q.removeLast();
q.addLast(i);
}
b[0] = a[q.peekFirst()];
for (int i=w; i
while (!q.isEmpty() && q.peekFirst()<=i-w) q.pop();
while (!q.isEmpty() && a[q.peekLast()]<=a[i]) q.removeLast();
q.addLast(i);
b[i-w+1] = a[q.peekFirst()];
}
return b;
}
如果有问题，去读ihasleetcode的网站。 |
b******v
发帖数: 1493 | 6 时间复杂性是什么？
【在 g**********y 的大作中提到】
: public int[] getWindowMax(int[] a, int w) {
: int[] b = new int[a.length - w + 1];
:
: ArrayDeque q = new ArrayDeque();
: for (int i=0; i: while (!q.isEmpty() && a[q.peekLast()]<=a[i]) q.removeLast();
: q.addLast(i);
: }
:
: b[0] = a[q.peekFirst()];
|
y*****z
发帖数: 9 | |
R******9
发帖数: 267 | 8 #include
#include
#include
using namespace std;
void PrintMaxInWindow(int a[], int n, int k){
set s;
int i=0;
for(;i
s.insert(a[i]);
set::reverse_iterator rit;
for(;i<=n;i++){
rit = s.rbegin();
cout<<*rit<<"\t";
s.erase(a[i-k]);
s.insert(a[i]);
}
}
【在 r***6 的大作中提到】
: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。
|
h*********r
发帖数: 74 | |
b***z
发帖数: 921 | 10 Use max-heap.
【在 r***6 的大作中提到】
: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。
|
|
|
P***P
发帖数: 1387 | 11 这题o(n)
就是implement a queue with getMax().
有点像crack150里面的stack with getMax()
public void addLast(T data) {
// insert data to the data queue.
dataQ.add(data);
// adjust the auxiliary queue.
while (!auxiQ.isEmpty() && auxiQ.getLast().compareTo(data) < 0) {
auxiQ.removeLast();
}
auxiQ.add(data); //append to the end.
}
public T getMax() {
return auxiQ.getFirst();
}
public T removeFirst() {
T data = dataQ.removeFirst();
// adjust the auxiliary queue. Because the previous max is removed, the
// head (which is the current max) should be removed too.
if (data == auxiQ.getFirst()) {
auxiQ.removeFirst();
}
return data;
} |
b***u
发帖数: 12010 | 12 可以用c++的map，每次存 reverse iterator的第一个，删find i-2
不过好像挺作弊。
【在 r***6 的大作中提到】
: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。
|
b***u
发帖数: 12010 | 13 heap找arr[i-3]不是很容易吧。
【在 b***e 的大作中提到】
: use heap?
|
b***u
发帖数: 12010 | 14 set好像不是sorted的吧？要用map
【在 R******9 的大作中提到】
: #include
: #include
: #include
: using namespace std;
: void PrintMaxInWindow(int a[], int n, int k){
: set s;
: int i=0;
: for(;i: s.insert(a[i]);
: set::reverse_iterator rit;
|
z******t
发帖数: 59 | 15 Share a blog with two solutions of this problem:
http://codercareer.blogspot.com/2012/02/no-33-maximums-in-slidi
Enjoy it:)
【在 r***6 的大作中提到】
: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。
|
r***6
发帖数: 15 | 16 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
大值。
例如，
有数组 2，3，4，2，6，7，8，2，4，1，2，3
k = 3
输出
4，4，6，7，8，8，8，4，4，4
有什么好一点的解法吗。 |
b***e
发帖数: 15201 | 17 use heap?
【在 r***6 的大作中提到】
: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。
|
n**4
发帖数: 719 | 18 use a queue
keep the biggest value at the head of the queue |
P*A
发帖数: 189 | 19 Maintain a Binary Search Tree,
with a pointer to the max node,
Every time you insert a new element, update the pointer if necessary.
【在 r***6 的大作中提到】
: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。
|
g**********y
发帖数: 14569 | 20 public int[] getWindowMax(int[] a, int w) {
int[] b = new int[a.length - w + 1];
ArrayDeque q = new ArrayDeque();
for (int i=0; i
while (!q.isEmpty() && a[q.peekLast()]<=a[i]) q.removeLast();
q.addLast(i);
}
b[0] = a[q.peekFirst()];
for (int i=w; i
while (!q.isEmpty() && q.peekFirst()<=i-w) q.pop();
while (!q.isEmpty() && a[q.peekLast()]<=a[i]) q.removeLast();
q.addLast(i);
b[i-w+1] = a[q.peekFirst()];
}
return b;
}
如果有问题，去读ihasleetcode的网站。 |
|
|
b******v
发帖数: 1493 | 21 时间复杂性是什么？
【在 g**********y 的大作中提到】
: public int[] getWindowMax(int[] a, int w) {
: int[] b = new int[a.length - w + 1];
:
: ArrayDeque q = new ArrayDeque();
: for (int i=0; i: while (!q.isEmpty() && a[q.peekLast()]<=a[i]) q.removeLast();
: q.addLast(i);
: }
:
: b[0] = a[q.peekFirst()];
|
y*****z
发帖数: 9 | |
R******9
发帖数: 267 | 23 #include
#include
#include
using namespace std;
void PrintMaxInWindow(int a[], int n, int k){
set s;
int i=0;
for(;i
s.insert(a[i]);
set::reverse_iterator rit;
for(;i<=n;i++){
rit = s.rbegin();
cout<<*rit<<"\t";
s.erase(a[i-k]);
s.insert(a[i]);
}
}
【在 r***6 的大作中提到】
: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。
|
h*********r
发帖数: 74 | |
b***z
发帖数: 921 | 25 Use max-heap.
【在 r***6 的大作中提到】
: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。
|
P***P
发帖数: 1387 | 26 这题o(n)
就是implement a queue with getMax().
有点像crack150里面的stack with getMax()
public void addLast(T data) {
// insert data to the data queue.
dataQ.add(data);
// adjust the auxiliary queue.
while (!auxiQ.isEmpty() && auxiQ.getLast().compareTo(data) < 0) {
auxiQ.removeLast();
}
auxiQ.add(data); //append to the end.
}
public T getMax() {
return auxiQ.getFirst();
}
public T removeFirst() {
T data = dataQ.removeFirst();
// adjust the auxiliary queue. Because the previous max is removed, the
// head (which is the current max) should be removed too.
if (data == auxiQ.getFirst()) {
auxiQ.removeFirst();
}
return data;
} |
b***u
发帖数: 12010 | 27 可以用c++的map，每次存 reverse iterator的第一个，删find i-2
不过好像挺作弊。
【在 r***6 的大作中提到】
: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。
|
b***u
发帖数: 12010 | 28 heap找arr[i-3]不是很容易吧。
【在 b***e 的大作中提到】
: use heap?
|
b***u
发帖数: 12010 | 29 set好像不是sorted的吧？要用map
【在 R******9 的大作中提到】
: #include
: #include
: #include
: using namespace std;
: void PrintMaxInWindow(int a[], int n, int k){
: set s;
: int i=0;
: for(;i: s.insert(a[i]);
: set::reverse_iterator rit;
|
z******t
发帖数: 59 | 30 Share a blog with two solutions of this problem:
http://codercareer.blogspot.com/2012/02/no-33-maximums-in-slidi
Enjoy it:)
【在 r***6 的大作中提到】
: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。
|
|
|
t*****j
发帖数: 1105 | 31 用数组实现的Q...
当然咯，用vector可以省去很多code。
void subMost(int* parentArray, int parentSize, int childSize)
{
int* valueArray = new int[childSize];
int* positionArray = new int[childSize];
int actualSize = 0;
int childFrontIndex = 0;
int childEndIndex = -1;
for(int i=0; i< parentSize+childSize-1; i++)
{
if(i>=childSize)
{
if(positionArray[childFrontIndex] == i-childSize)
{
childFrontIndex = (childFrontIndex++)%childSize;
actualSize --;
}
}
if(i < parentSize)
{
while((valueArray[childEndIndex] < parentArray[i]) && (
actualSize >0))
{
childEndIndex --;
actualSize --;
if((childEndIndex < 0) && (actualSize > 0) )
{
childEndIndex = childSize-1;
}
}
childEndIndex = (childEndIndex ++)%childSize;
valueArray[childEndIndex] = parentArray[i];
positionArray[childEndIndex] = i;
actualSize = actualSize++;
}
cout << valueArray[childFrontIndex] << endl;
}
delete valueArray;
delete positionArray;
}
test过了...
【在 r***6 的大作中提到】
: 有一无序数组长度为n，以及一个可以从左到右移动的子数组，长度为k。
: 假设子数组起始位置为0，要求在子数组从最左到最右的移动过程中，输出子数组的最
: 大值。
: 例如，
: 有数组 2，3，4，2，6，7，8，2，4，1，2，3
: k = 3
: 输出
: 4，4，6，7，8，8，8，4，4，4
: 有什么好一点的解法吗。
|
g*********e
发帖数: 14401 | 32 leetcode上有这道题，貌似是两个queue |
p*****2
发帖数: 21240 | 33
我前几天做了，好像一个就可以了。
【在 g*********e 的大作中提到】
: leetcode上有这道题，貌似是两个queue
|
M***t
发帖数: 1636 | 34 你看2月16号的帖子，何海涛本人给了他的解
【在 p*****2 的大作中提到】
:
: 我前几天做了，好像一个就可以了。
|
