详细信息:
-
在给定数组
numbers = {2, 7, 8, 5, 1, 6, 3, 9, 4}.
判断以下条件的情况下,两个条件都应满足. -
如果为
arr[i – 1] < arr[i] > arr[i + 1]
,其中1<;i<;N-1,则arr[i]是峰值元素. -
如果
arr[0] > arr[1], then arr[0]
是峰值元素,其中N是数组的大小. -
如果
arr[N – 2] < arr[N – 1], then arr[N – 1]
是峰值元素,其中N是数组的大小. -
如果数组中有
more than one peak element
个,则需要打印其中的minimum value
个.
示例:
1st Iteration - 8, 6, 9 are peak values.
Remove the smallest ele. Remove 6.
New arr {2, 7, 8, 5, 1, 3, 9, 4}. Output Arr - {6}
2nd Iteration - 8, 9 are peak values.
Remove the smallest ele. Remove 8.
New arr {2, 7, 5, 1, 3, 9, 4}. Output Arr - {6, 8}
3rd Iteration - 7, 9 are peak values.
Remove the smallest ele. Remove 7.
New arr {2, 5, 1, 3, 9, 4}. Output Arr - {6, 7, 8}
4th Iteration - 5, 9 are peak values.
Remove the smallest ele. Remove 5.
New arr {2, 1, 3, 9, 4}. Output Arr - {6, 7, 8, 5}
5th Iteration - 2, 9 are peak values.
Remove the smallest ele. Remove 2.
New arr {1, 3, 9, 4}. Output Arr - {6, 7, 8, 5, 2}
6th Iteration - 9 are peak values.
Remove the smallest ele. Remove 9.
New arr {1, 3, 4}. Output Arr - {6, 7, 8, 5, 2, 9}
7th Iteration - 4 are peak values.
Remove the smallest ele. Remove 4.
New arr {1, 3}. Output Arr - {6, 7, 8, 5, 2, 9, 4}
8th Iteration - 3 are peak values.
Remove the smallest ele. Remove 3.
New arr {1}. Output Arr - {6, 7, 8, 5, 2, 9, 4, 3}
9th Iteration - 1 are peak values.
Remove the smallest ele. Remove 1.
New arr {1}. Output Arr - {6, 7, 8, 5, 2, 9, 4, 3, 1}
Output: {6, 8, 7, 5, 2, 9, 4, 3, 1}
我的代码:
nums = [2, 7, 8, 5, 1, 6, 3, 9, 4]
def deleteMinimalPeaks(nums):
from queue import PriorityQueue as pq
if len(nums) <= 1:
return nums
peakq = pq()
out = []
n = len(nums)
ridx = [i+1 for i in range(n)]
lidx = [i-1 for i in range(n)]
nums.append(-1)
if nums[0] > nums[1]:
peakq.put((nums[0], 0))
if nums[n-1] > nums[n-2]:
peakq.put((nums[n-1], n-1))
for i in range(1, n-1):
if nums[i] > nums[i-1] and nums[i] > nums[i+1]:
peakq.put((nums[i], i))
if peakq.empty():
nums.pop()
return nums[::-1]
while(not peakq.empty()):
val, idx = peakq.get()
out.append(val)
if len(out) == len(nums):
break
if ridx[idx] <= n-1:
lidx[ridx[idx]] = lidx[idx]
if lidx[idx] >= 0:
ridx[lidx[idx]] = ridx[idx]
if ridx[idx] <= n-1 \
and nums[ridx[idx]] > nums[ridx[ridx[idx]]] \
and nums[ridx[idx]] > nums[lidx[ridx[idx]]]:
peakq.put( (nums[ridx[idx]], ridx[idx]) )
if lidx[idx] >= 0 \
and nums[lidx[idx]] > nums[lidx[lidx[idx]]] \
and nums[lidx[idx]] > nums[ridx[lidx[idx]]]:
peakq.put( (nums[lidx[idx]], lidx[idx]) )
return out
deleteMinimalPeaks(nums)
问题:
代码给出了正确的结果.
然而,有没有一种更有攻击性的方式来写innermost while loop?