一道有关分治算法的题目，求思路
来源：3-9 归并排序和快速排序的衍生问题
Lincolnshan
2020-04-26
先谢谢bobo老师
一道网上看到的题，求点拨：
A = [h0,h1,h2,h3,h4,…,hn−1] 代表一个山脉，设计一个分治算法，生成两个数组：
L[0…n − 1] L[x]代表从A[x]向左看时，离x距离最近且比A[x]高的山，若没有比A[x]高的山则L[x} = None。
R[0…n − 1] 同理。
样例：
Input: A=[5,2,6,8,1,4,3,9]
Output:
- L=[None, 0, None, None, 3, 3, 5, None]
- R=[2, 2, 3, 7, 5, 7, 7, None]
Input: A=[4,2,3,1,8,5,6,9]
Output:
- L=[None, 0, 0, 2, None, 4, 4, None]
- R=[4, 2, 4, 4, 7, 6, 7, None]
Input: A=[8,2,1]
Output:
- L=[None, 0, 1]
- R=[None, None, None]
写回答
1回答
-
liuyubobobo
2020-04-27
抱歉，我无法在课程的问答区做到所有同学随便拿出一个算法题，我马上就进行解答。否则我就没法做别的事情了，请谅解。
这个课程的问答区只针对课程内容，包括 Leetcode 的问题进行答疑。课程针对算法面试设计，Leetcode 现在也已经有超过 1000 个问题了，相信近乎涵盖了算法面试的方方面面的各种问题，我相信足够了。对于其他地方的问题，请到相关的讨论区进行探讨。
请谅解。
继续加油！：）
112020-04-27
相似问题