如何在Erlang中寻找允许两端平坦的最宽山谷

问题描述 #

给定一组代表区块大小的数字列表，需找出其中形状最宽的山谷。与常规山谷不同，本问题允许山谷两端平坦（例如[5,5]仍视为山谷端点）。

示例 #

• [1, 5, 5, 2, 8] => 最宽山谷为 [5, 5, 2, 8]
• [2, 6, 8, 5] => 最宽山谷为 [2,6,8]
• [9, 8, 13, 13, 2, 2, 15, 17] => 最宽山谷为 [13, 13, 2, 2, 15, 17]

本人已在其他语言实现该功能，但因Erlang的递归特性，现寻求该问题的Erlang实现方案。

Erlang实现方案 #

核心思路 #

1. 预处理列表，提取关键转折点（保留连续相同元素的首尾端点），简化递归处理的复杂度；
2. 递归遍历所有可能的山谷结构：山谷需满足「先非递增到谷底，再非递减」的形态；
3. 遍历过程中记录最长山谷，最终返回长度最大的结果（长度相同时返回第一个遇到的）。

代码实现 #

-module(valley).
-export([widest_valley/1]).

widest_valley(List) ->
    KeyPoints = extract_key_points(List),
    InitialValley = case find_first_valley(KeyPoints) of
        undefined -> [];
        V -> V
    end,
    find_widest_valley(KeyPoints, InitialValley).

% 提取关键转折点：保留连续相同元素的首尾
extract_key_points([]) -> [];
extract_key_points([H|T]) ->
    extract_key_points(T, H, [H]).

extract_key_points([], _Last, Acc) -> lists:reverse(Acc);
extract_key_points([H|T], Last, Acc) when H =:= Last ->
    case Acc of
        [Last|_] -> extract_key_points(T, Last, Acc);
        _ -> extract_key_points(T, Last, [Last|Acc])
    end;
extract_key_points([H|T], Last, Acc) ->
    case lists:reverse(Acc) of
        [Last|_] -> extract_key_points(T, H, [H, Last|Acc]);
        _ -> extract_key_points(T, H, [H|Acc])
    end.

% 找到第一个符合条件的山谷
find_first_valley([]) -> undefined;
find_first_valley([_]) -> undefined;
find_first_valley([A,B|T]) ->
    case is_valley_start([A,B|T]) of
        {true, Valley} -> Valley;
        false -> find_first_valley([B|T])
    end.

% 判断是否为山谷起始并返回完整山谷
is_valley_start(List) ->
    {Descending, Rest} = take_non_increasing(List),
    if
        length(Descending) < 1; length(Rest) < 1 -> false;
        true ->
            {Ascending, _} = take_non_decreasing(Rest),
            case length(Ascending) >= 1 of
                true -> {true, Descending ++ Ascending};
                false -> false
            end
    end.

% 提取非递增前缀
take_non_increasing([]) -> {[], []};
take_non_increasing([H|T]) ->
    take_non_increasing(T, H, [H]).

take_non_increasing([], _Last, Acc) -> {lists:reverse(Acc), []};
take_non_increasing([H|T], Last, Acc) when H =< Last ->
    take_non_increasing(T, H, [H|Acc]);
take_non_increasing(Rest, _Last, Acc) -> {lists:reverse(Acc), Rest}.

% 提取非递减前缀
take_non_decreasing([]) -> {[], []};
take_non_decreasing([H|T]) ->
    take_non_decreasing(T, H, [H]).

take_non_decreasing([], _Last, Acc) -> {lists:reverse(Acc), []};
take_non_decreasing([H|T], Last, Acc) when H >= Last ->
    take_non_decreasing(T, H, [H|Acc]);
take_non_decreasing(Rest, _Last, Acc) -> {lists:reverse(Acc), Rest}.

% 递归遍历找最宽山谷
find_widest_valley([], CurrentWidest) -> CurrentWidest;
find_widest_valley([_], CurrentWidest) -> CurrentWidest;
find_widest_valley(List, CurrentWidest) ->
    case is_valley_start(List) of
        {true, Valley} ->
            NewWidest = if
                length(Valley) > length(CurrentWidest) -> Valley;
                true -> CurrentWidest
            end,
            find_widest_valley(tl(List), NewWidest);
        false ->
            find_widest_valley(tl(List), CurrentWidest)
    end.

代码说明 #

• extract_key_points/1：处理连续相同元素，保留首尾端点，既符合题目对平坦端点的要求，又减少冗余元素；
• take_non_increasing/1、take_non_decreasing/1：分别提取非递增、非递减前缀，用于识别山谷的下坡和上坡段；
• find_widest_valley/2：递归遍历所有可能的起始点，不断更新当前最宽山谷。

测试示例 #

1> valley:widest_valley([1,5,5,2,8]).
[5,5,2,8]
2> valley:widest_valley([2,6,8,5]).
[2,6,8]
3> valley:widest_valley([9,8,13,13,2,2,15,17]).
[13,13,2,2,15,17]

内容的提问来源于stack exchange，提问作者sayonara