แนวคิด
สำหรับอาร์เรย์ของจำนวนเต็มที่กำหนด หน้าที่ของเราคือกำหนดความต่างสัมบูรณ์สูงสุดระหว่างองค์ประกอบที่เล็กกว่าทางซ้ายและทางขวาที่ใกล้ที่สุดของทุกองค์ประกอบในอาร์เรย์ ควรสังเกตว่าหากไม่มีองค์ประกอบที่เล็กกว่าทางด้านขวาหรือด้านซ้าย ด้านข้างขององค์ประกอบใด ๆ จากนั้นเรายอมรับศูนย์เป็นองค์ประกอบที่เล็กกว่า ในที่นี้ ตัวอย่างเช่น สำหรับองค์ประกอบด้านซ้ายสุด องค์ประกอบที่เล็กกว่าทางด้านซ้ายสุดจะถูกตั้งค่าเป็น 0 ในทำนองเดียวกัน สำหรับองค์ประกอบทางขวาสุด องค์ประกอบที่เล็กกว่าทางด้านขวาจะถูกตั้งค่าเป็น 0
อินพุต
arr[] = {3, 2, 9} ผลลัพธ์
2
เหลือ LS ที่เล็กกว่า[] {0, 0, 2}
RS เล็กลง[] {2, 0, 0}
ความแตกต่างสูงสุดของ abs(LS[i] - RS[i]) =2 - 0 =2
อินพุต
arr[] = {3, 5, 9, 8, 8, 10, 4} ผลลัพธ์
4
เหลือ LS ที่เล็กกว่า[] ={0, 3, 5, 5, 5, 8, 3}
RS ที่เล็กกว่าด้านขวา[] ={0, 4, 8, 4, 4, 4, 0}
ความแตกต่างสูงสุดของ abs(LS[i] - RS[i]) =8 - 4 =4
วิธีการ
เราใช้วิธีแก้ปัญหาง่ายๆ โดยที่งานของเราคือค้นหาองค์ประกอบที่เล็กกว่าด้านซ้ายและขวาที่ใกล้ที่สุดตลอดกาล และหลังจากนั้นอัปเดตความแตกต่างสูงสุดระหว่างองค์ประกอบที่เล็กกว่าด้านซ้ายและขวา ซึ่งจะสิ้นเปลืองเวลา O(n^2)
อีกครั้งเราใช้โซลูชันที่มีประสิทธิภาพซึ่งกินเวลา O(n) ที่นี่เราใช้สแต็ก ส่วนที่น่าสนใจตรงที่นี้คือ เราคำนวณทั้งทางซ้ายและขวาที่เล็กกว่าและทางขวาที่เล็กกว่าโดยใช้ฟังก์ชันเดียวกัน
สมมติว่าอาร์เรย์อินพุตเป็น 'Array[]' และขนาดของอาร์เรย์เป็น 'n'
กำหนดองค์ประกอบที่เล็กกว่าทั้งหมดทางด้านซ้าย
- สร้างสแต็กว่างใหม่ S และอาร์เรย์ LS[]
- ตอนนี้สำหรับทุกองค์ประกอบ 'Array[i]' ในอินพุต Array[] โดยที่ 'i' เปลี่ยนจาก 0 เป็น n-1
- ในขณะที่ S ไม่ว่าง และองค์ประกอบบนสุดของ S มากกว่าหรือเท่ากับ 'Array[i]':pop S
- ถ้า S ว่างเปล่า:'Array[i]' ไม่มีค่าน้อยกว่า LS[i] =0
- else:ค่าที่น้อยกว่าที่ใกล้ที่สุดสำหรับ 'Array[i]' คือ topof stackLS[i] =S.top()
- ดัน 'Array[i]' ไปที่ S
- กำหนดองค์ประกอบที่เล็กกว่าทั้งหมดทางด้านขวา
- ในอาร์เรย์แบบย้อนกลับครั้งแรก Array[] ตอนนี้หลังจากย้อนกลับอาร์เรย์ ทางขวาที่เล็กลงจะกลายเป็นทางซ้ายที่เล็กลง
- สร้างอาร์เรย์ RRS[] และทำซ้ำขั้นตอนที่ 1 และ 2 เพื่อเติม RRS (แทนที่ LS)
- เราเริ่มต้นผลลัพธ์เป็น -1 และติดตามทุก elementArray[i] ด้วยความเคารพของอาร์เรย์ที่กลับด้านที่เล็กกว่าสำหรับ Array[i] จะถูกเก็บไว้ที่ RRS[n-i-1]return result =max(result, LS[i]-RRS[n-i-1])
ตัวอย่าง
// C++ program to find the difference b/w left and
// right smaller element of every element in array
#include<bits/stdc++.h>
using namespace std;
// Shows function to fill left smaller element for every
// element of Array[0..n1-1]. These values are filled
// in SE1[0..n1-1]
void leftSmaller(int Array[], int n1, int SE1[]){
// Build an empty stack
stack<int>S1;
// Visit all array elements
// Calculate nearest smaller elements of every element
for (int i=0; i<n1; i++){
// Used to keep removing top element from S1 while the top
// element is greater than or equal to Array[i]
while (!S1.empty() && S1.top() >= Array[i])
S1.pop();
// Used to store the smaller element of current element
if (!S1.empty())
SE1[i] = S1.top();
// It has been seen that if all elements in S were greater than Array[i]
else
SE1[i] = 0;
// Used to push this element
S1.push(Array[i]);
}
}
// Shows function returns maximum difference b/w Left &
// right smaller element
int findMaxDiff(int Array[], int n1){
int LS1[n1]; // To store left smaller elements
// find left smaller element of every element
leftSmaller(Array, n1, LS1);
// Determine right smaller element of every element
// first reverse the array and do the same process
int RRS1[n1]; // Used to store right smaller elements in
// reverse array
reverse(Array, Array + n1);
leftSmaller(Array, n1, RRS1);
// Determine maximum absolute difference b/w LS1 & RRS1
// In the reversed array right smaller for Array[i] is
// stored at RRS1[n1-i-1]
int result1 = -1;
for (int i=0 ; i< n1 ; i++)
result1 = max(result1, abs(LS1[i] - RRS1[n1-1-i]));
// return maximum difference between LS1 & RRS1
return result1;
}
// Driver program
int main(){
int Array[] = {3, 5, 9, 8, 8, 10, 4};
int n = sizeof(Array)/sizeof(Array[0]);
cout << "Maximum diff : "
<< findMaxDiff(Array, n) << endl;
return 0;
} ผลลัพธ์
Maximum diff : 4
