The higher mountain partition algorithm, recently-CodePudding

Array A=[a0, a1, a2, a3, a4,..., the an - 1) represent the peak height of each peak, with partition method find each peak on the left side is higher than their peaks and higher than they are on the right position of the peaks of the index of , for example:
Input: A=,3,2,7,4,9 [1]
Output:
L=[None, None, 2, None, 3, None] R=[1, 3, 3, 5, 5, None], describe the algorithm and the analysis of time complexity,

CodePudding user response:

If can use O (n) of space, time complexity to O (n), without partition method
From left to right scan, save from high to low peak information
Start time,
Read the first '1', because is empty, the result is None, keep the '1'.
Read the second '3', with a comparative value, no bigger than 3, the result is None, replace with '3' saved '1'
Read the third '2', and save the '3', is smaller than 3, the results of 3, 2 save up
Read the fourth '7', save the '3', '2', to replace any result to None, with seven save 3 and 2
.

Similarly from right to left to scan it again

CodePudding user response:

reference 1st floor android2008 response:

if can use O (n) of space, time complexity to O (n), without partition method
From left to right scan, save from high to low peak information
Start time,
Read the first '1', because is empty, the result is None, keep the '1'.
Read the second '3', with a comparative value, no bigger than 3, the result is None, replace with '3' saved '1'
Read the third '2', and save the '3', is smaller than 3, the results of 3, 2 save up
Read the fourth '7', save the '3', '2', to replace any result to None, with seven save 3 and 2
.

Similarly from right to left to scan again

You may be the understanding of O (n) is wrong, you this algorithm is O (n ^ 2), not O (n), two arrays of traverse your cost also need time...

O (n) algorithm is to make full use of drab stack the data structure,
What is called monotonic stack please search on the net,
A monotone increasing stack, a monotone decreasing stack, save the left and right, respectively, and then two arrays LR respectively record the results
Traverse from left to right again, first with a monotone decreasing stack trace left high peak, L is lower than the stack is recorded into stack, otherwise circulation stacks, then recorded the L,
Traverse from right to left, again with a monotone increasing stack trace on the right side of the high peak, in the same way,

CodePudding user response:

reference lx3275852 reply: 3/f

Quote: refer to 1st floor android2008 response:

If can use O (n) of space, time complexity to O (n), without partition method
From left to right scan, save from high to low peak information
Start time,
Read the first '1', because is empty, the result is None, keep the '1'.
Read the second '3', with a comparative value, no bigger than 3, the result is None, replace with '3' saved '1'
Read the third '2', and save the '3', is smaller than 3, the results of 3, 2 save up
Read the fourth '7', save the '3', '2', to replace any result to None, with seven save 3 and 2
.

Similarly from right to left to scan again

You may be the understanding of O (n) is wrong, you this algorithm is O (n ^ 2), not O (n), two arrays of traverse your cost also need time...

O (n) algorithm is to make full use of drab stack the data structure,
What is called monotonic stack please search on the net,
A monotone increasing stack, a monotone decreasing stack, save the left and right, respectively, and then two arrays LR respectively record the results
Traverse from left to right again, first with a monotone decreasing stack trace left high peak, L is lower than the stack is recorded into stack, otherwise circulation stacks, then recorded the L,
Traverse from right to left, again with a monotone increasing stack trace on the right side of the high peak, in the same way,

Every time is more than 1 will be deleted (number 1) data, how not O (N)? I don't know you say how to O (N ^ 2) conclusion,

CodePudding user response:

reference 4 floor android2008 response:

every time is more than 1 will be deleted (number 1) data, how not O (N)? I don't know what you said how to O (N ^ 2) conclusion,

That may be I didn't quite understand your algorithm is described,

Each time according to your description, met Numbers than you save big, all need to traverse to find, and then replace your this number...
You wrote the fourth step, "read a fourth '7', save the '3', '2', the results to None, with 7 replace save 3 and 2"
To 7, to replace 3 and 2, this is not just need to traverse again,,

CodePudding user response:

reference 5 floor lx3275852 reply:

Quote: refer to 4th floor android2008 response:

Every time is more than 1 will be deleted (number 1) data, how not O (N)? I don't know what you said how to O (N ^ 2) conclusion,

That may be I didn't quite understand your algorithm is described,

Each time according to your description, met Numbers than you save big, all need to traverse to find, and then replace your this number...
You wrote the fourth step, "read a fourth '7', save the '3', '2', the results to None, with 7 replace save 3 and 2"
To 7, to replace 3 and 2, this is not just need to traverse again,,

May I say not clear.
Seems to traverse it again every time, but is also 2 n times, most times because every time don't need to traverse, and traversal, the more the more we deleted.
Such as current saved five: 10 8 6 April 2, new data is 9, although to compare 5 times, 8,6,4,2 will be deleted, but retain only 10, 9, behind the traversal time length is small.

CodePudding user response:

refer to 6th floor android2008 response:

maybe I said not clear.
Seems to traverse it again every time, but is also 2 n times, most times because every time don't need to traverse, and traversal, the more the more we deleted.
Such as current saved five: 10 8 6 April 2, new data is 9, although to compare 5 times, 8,6,4,2 will be deleted, but retain only 10, 9, behind traversed the length is small.

Suit you, you this description is not monotonous stack, and I said 3 l have what distinction,,,
But you this description, if you can't dull stack description, increasing decline is not described, stack does not describe...