資料結構
網路
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 次瀏覽
廣告