解法一：时间复杂度为O(N*N) ，暴力所有分组情况。

解法二：时间复杂度为O(2*N)。

思路：对数组预处理，构造两个辅助数组——左区间数组，右区间数组。将 [0, i ] 的最大值存入左区间数组记为L[i]。 将 ( i , N ] 的最大值记为R[ i ]，最后遍历数组。

解法三：时间复杂度O(N)。

思路：找出数组中最大的那个数max，用max减去数组两端较小的那个数所得的差值就是答案；如果max在端点就用max减去另一个端点的值就是答案。证明很简单，让最小数单独成为一个区间就是答案了。

 

 

题目大意：找出数组内任意一个局部最小值，也就是数学中的极小值点所在的下标。

解题思路：二分求解。先判断两端是否是极小值点，如果不是，二分中间部分。

 

 

 

解题思路：（二叉树，中序行遍法）先按规律折几次。我们发现第 n 次对折后的折痕数为2^n -1 个，并且我们会发现如下规律：

于是我们发现这是一个左节点始终为down，右节点始终为up的二叉树。结果按中序行遍法输出就行。