龙空技术网

求数组先升序再降序的最大值-C++

篮球鉴赏家小华 107

前言:

而今大家对“c数组升序排序”大致比较关心,朋友们都需要分析一些“c数组升序排序”的相关内容。那么小编也在网摘上汇集了一些关于“c数组升序排序””的相关内容,希望同学们能喜欢,同学们一起来学习一下吧!

一个数组先升序再降序,用最优时间复杂度,求最大值?

例1:

[1,2,2,2,2,3,1]

输出3

例2:

[1,3,5,6,9,4,2]

输出 9

例3:

[1,3,2]

输出3

#include <vector>#include <iostream>#include <string>using namespace std;class Solution {public:    int solve(vector<int>& arr, int left , int right)    {        while (left <= right)        {            int mid = left + (right - left) / 2;            if(left == right) return arr[left];            if((mid == 0 || mid == arr.size() - 1) ||             (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]))            {                return arr[mid];            }            else if (arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1])            {//上升趋势                left = mid + 1;            }            else if (arr[mid - 1] > arr[mid] && arr[mid] > arr[mid + 1])            {//下降趋势                right = mid - 1;            }              else            {//平滑趋势                int one = solve(arr, left, mid - 1);                int two = solve(arr, mid + 1, right);                return one > two ? one:two;            }        }        return -1;    }    };int main(int argc, char **argv){    Solution solution;    vector<int> arr = {1,3,5,6,9,4,2};    vector<int> arr1 = {1,2,2,2,3,1};    vector<int> arr2 = {1,3,2};    int length = arr2.size();    int ret = solution.solve(arr2, 0, length - 1);    cout<<ret<<endl;    return 0;}

标签: #c数组升序排序