数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究查找子数组是否形式为 C++ 中的山峰
在这个问题中，我们给定一个整数数组 arr[] 和一个范围。我们的任务是 查找子数组是否形式为山峰。
我们举一个例子来理解这个问题，
Input : arr[] = {1, 4, 2, 5, 6, 7, 3, 0}, range = [2, 7]
Output : Yes说明−
Subarray of range = {2, 5, 6, 7, 3, 0}
The values first increase and then decrease.求解方法
通过使用额外数组是一个求解该问题的简单方案。我们将找出数组中每个元素的最后一个递增元素的索引，并对递减值进行同样的操作。然后再检查指定时间范围内的山峰。
示例
程序来说明我们求解方法的工作原理
#include <iostream>
using namespace std;
int processArray(int arr[], int N, int left[], int right[]){
left[0] = 0;
int increasingValR = 0;
for (int i = 1; i < N; i++){
if (arr[i] > arr[i - 1])
increasingValR = i;
left[i] = increasingValR;
}
right[N - 1] = N - 1;
int decreasingValL = N - 1;
for (int i = N - 2; i >= 0; i--){
if (arr[i] > arr[i + 1])
decreasingValL = i;
right[i] = decreasingValL;
}
}
bool isMountainSubArray(int arr[], int left[], int right[], int L, int R){
return (right[L] >= left[R]);
}
int main(){
int arr[] = {2, 3, 2, 4, 4, 6, 3, 2};
int N = sizeof(arr) / sizeof(int);
int left[N], right[N];
processArray(arr, N, left, right);
int L = 0;
int R = 2;
if (isMountainSubArray(arr, left, right, L, R))
cout<<"The subarray is in mountain form";
else
cout<<"The subarray is not in mountain form";
return 0;
}输出
The subarray is in mountain form
更新于：01-二月-2022
127 次浏览
广告