codewars（python）練習(xí)筆記二十二：Pick peaks(求峰值)

題目

In this kata, you will write a function that returns the positions and the values of the "peaks" (or local maxima) of a numeric array.

For example, the array arr = [0, 1, 2, 5, 1, 0] has a peak at position 3 with a value of 5 (since arr[3] equals 5).

The output will be returned as an object with two properties: pos and peaks. Both of these properties should be arrays. If there is no peak in the given array, then the output should be {pos: [], peaks: []}.

Example: pickPeaks([3, 2, 3, 6, 4, 1, 2, 3, 2, 1, 2, 3]) should return {pos: [3, 7], peaks: [6, 3]} (or equivalent in other languages)
All input arrays will be valid integer arrays (although it could still be empty), so you won't need to validate the input.

The first and last elements of the array will not be considered as peaks (in the context of a mathematical function, we don't know what is after and before and therefore, we don't know if it is a peak or not).

Also, beware of plateaus !!! [1, 2, 2, 2, 1] has a peak while [1, 2, 2, 2, 3] does not. In case of a plateau-peak, please only return the position and value of the beginning of the plateau. For example: pickPeaks([1, 2, 2, 2, 1]) returns {pos: [1], peaks: [2]} (or equivalent in other languages)

題目大意：

求出數(shù)組的峰值和峰值對(duì)應(yīng)的位置。
例如：[3, 2, 3, 6, 4, 1, 2, 3, 2, 1, 2, 3]

屏幕快照 2018-05-28 下午5.31.21.png

去除左右兩端的峰值之后，發(fā)現(xiàn)峰值的位置出現(xiàn)在6，3 兩個(gè)值，其對(duì)應(yīng)的位置為 3，7.那么，應(yīng)該輸出的是 {pos: [3, 7], peaks: [6, 3]} 。
注意：

1. 入?yún)閕nteger數(shù)組，不用驗(yàn)證數(shù)組
2. 峰值，則輸出 {pos: [], peaks: []}
3. 兩端的峰值
4. [1, 2, 2, 2, 1] 有峰值而 [1, 2, 2, 2, 3] 沒(méi)有。 [1, 2, 2, 2, 1]的峰值為 {pos: [1], peaks: [2]} .

Sample Tests:

Test.it('should support finding peaks')
Test.assert_equals(pick_peaks([1,2,3,6,4,1,2,3,2,1]), {"pos":[3,7], "peaks":[6,3]})

Test.it('should support finding peaks, but should ignore peaks on the edge of the array')
Test.assert_equals(pick_peaks([3,2,3,6,4,1,2,3,2,1,2,3]), {"pos":[3,7], "peaks":[6,3]})

Test.it('should support finding peaks; if the peak is a plateau, it should only return the position of the first element of the plateau')
Test.assert_equals(pick_peaks([3,2,3,6,4,1,2,3,2,1,2,2,2,1]), {"pos":[3,7,10], "peaks":[6,3,2]})

Test.it('should support finding peaks; if the peak is a plateau, it should only return the position of the first element of the plateau')
Test.assert_equals(pick_peaks([2,1,3,1,2,2,2,2,1]), {"pos":[2,4], "peaks":[3,2]})

Test.it('should support finding peaks, but should ignore peaks on the edge of the array')
Test.assert_equals(pick_peaks([2,1,3,1,2,2,2,2]), {"pos":[2], "peaks":[3]})

我的解法

#!/usr/bin/python

def pick_peaks(arr):
    pos = [] 
    peaks = []
    for i in range(0,len(arr)):
        if i == 0 or i == len(arr)-1:
            pass
        elif arr[i] > arr[i-1] and arr[i] > arr[i+1]:
            pos.append(i)
            peaks.append(arr[i])
        elif arr[i] > arr[i-1] and arr[i] == arr[i+1]:
            for j in range(i,len(arr)):
                if arr[j] < arr[i]:
                    pos.append(i)
                    peaks.append(arr[i])
                if arr[j] != arr[i]:
                    i = j
                    break
    return {"pos":pos,"peaks":peaks}

照例，codewar 上的高贊解法：

def pick_peaks(arr):
    peak, pos = [], []
    res = { "peaks":[], "pos":[] }
    for i in range(1, len(arr)) :
        if arr[i]>arr[i-1] :
            peak, pos = [arr[i]], [i]
        elif arr[i]<arr[i-1] :
            res["peaks"] += peak
            res["pos"] += pos
            peak, pos = [], []
    return res

的確，這是一個(gè)壓棧出棧的思路，我沒(méi)想清楚。