ในปัญหานี้ เราได้รับอาร์เรย์ของจำนวนเต็ม arr[] และช่วง งานของเราคือ ค้นหาว่า subarray อยู่ในรูปของภูเขาหรือไม่ .
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
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
