แนวคิด
เมื่อได้รับอาร์เรย์ของจำนวนเต็ม งานของเราคือหาความต่างสัมบูรณ์สูงสุดระหว่าง nearest left smaller element และ right smaller element ของทุกองค์ประกอบในอาร์เรย์ ควรสังเกตว่า หากไม่มี smaller element ด้านขวาหรือซ้ายขององค์ประกอบใดๆ เราจะรับศูนย์เป็น smaller element ที่นี่ ตัวอย่างเช่น สำหรับ leftmost element nearest smaller element ด้านซ้ายถูกตั้งเป็น 0 อย่างเดียวกัน สำหรับ rightmost elements smaller element ด้านขวาถูกตั้งเป็น 0
อินพุต
arr[] = {3, 2, 9}เอาต์พุต
2
Left smaller LS[] {0, 0, 2}
Right smaller RS[] {2, 0, 0}
Maximum Diff of abs(LS[i] - RS[i]) = 2 - 0 = 2
อินพุต
arr[] = {3, 5, 9, 8, 8, 10, 4}เอาต์พุต
4
Left smaller LS[] = {0, 3, 5, 5, 5, 8, 3}
Right smaller RS[] = {0, 4, 8, 4, 4, 4, 0}
Maximum Diff of abs(LS[i] - RS[i]) = 8 - 4 = 4
วิธีการ
เราใช้วิธีง่ายๆ ที่งานของเราคือหา nearest left และ right smaller elements สำหรับทุกองค์ประกอบ และหลังจากนั้นอัปเดตความต่างสูงสุดระหว่าง left และ right smaller element ซึ่งใช้เวลา O(n^2)
อีกครั้งเราใช้วิธีที่มีประสิทธิภาพซึ่งใช้เวลา O(n) ที่นี่เราใช้ stack สิ่งที่น่าสนใจที่นี่คือเราคำนวณ left smaller และ right smaller ทั้งคู่ด้วยฟังก์ชันเดียวกัน
สมมติ input array เป็น 'Array[]' และขนาดของอาร์เรย์เป็น 'n'
หา smaller elements ทั้งหมดด้านซ้าย
- สร้าง stack S ใหม่ว่างเปล่า และอาร์เรย์ LS[]
- ตอนนี้สำหรับทุกองค์ประกอบ 'Array[i]' ใน input Array[] โดยที่ 'i' ไปจาก 0 ถึง n-1
- while S ไม่ว่าง และ top element ของ S มากกว่าหรือเท่ากับ 'Array[i]': pop S
- if S ว่าง: 'Array[i]' ไม่มีค่าที่น้อยกว่าก่อนหน้า LS[i] = 0
- else: nearest smaller value ไปยัง 'Array[i]' คือ top of stack LS[i] = S.top()
- push 'Array[i]' ลง S
- หา smaller elements ทั้งหมดด้านขวา
- ก่อนอื่น reverse array Array[] ตอนนี้หลังจาก reverse array แล้ว right smaller จะกลายเป็น left smaller
- สร้างอาร์เรย์ RRS[] และทำซ้ำขั้นตอน 1 และ 2 เพื่อเติม RRS (แทนที่ LS)
- เราเริ่มต้น result เป็น -1 และทำสิ่งต่อไปนี้สำหรับทุกองค์ประกอบ Array[i] สำหรับ reversed array right smaller สำหรับ Array[i] จะถูกเก็บที่ RRS[n-i-1] คืนค่า result = max(result, LS[i]-RRS[n-i-1])
ตัวอย่างโค้ด
// โปรแกรม C++ เพื่อหาความต่างระหว่าง left และ // right smaller element ของทุกองค์ประกอบในอาร์เรย์ #include<bits/stdc++.h> using namespace std; // ฟังก์ชันแสดงการเติม left smaller element สำหรับทุก // องค์ประกอบของ Array[0..n1-1] ค่าเหล่านี้ถูกเติม // ใน SE1[0..n1-1] void leftSmaller(int Array[], int n1, int SE1[]){ // สร้าง empty stack stack<int>S1; // เยี่ยมชมทุกองค์ประกอบของอาร์เรย์ // คำนวณ nearest smaller elements ของทุกองค์ประกอบ for (int i=0; i<n1; i++){ // ใช้ลบ top element จาก S1 ขณะที่ top // element มากกว่าหรือเท่ากับ Array[i] while (!S1.empty() && S1.top() >= Array[i]) S1.pop(); // ใช้เก็บ smaller element ของ current element if (!S1.empty()) SE1[i] = S1.top(); // พบว่าถ้าองค์ประกอบทั้งหมดใน S มากกว่า Array[i] else SE1[i] = 0; // ใช้ push องค์ประกอบนี้ S1.push(Array[i]); } } // ฟังก์ชันคืนค่าความต่างสูงสุดระหว่าง Left & // right smaller element int findMaxDiff(int Array[], int n1){ int LS1[n1]; // เพื่อเก็บ left smaller elements // หา left smaller element ของทุกองค์ประกอบ leftSmaller(Array, n1, LS1); // หา right smaller element ของทุกองค์ประกอบ // ก่อนอื่น reverse array และทำกระบวนการเดียวกัน int RRS1[n1]; // ใช้เก็บ right smaller elements ใน // reverse array reverse(Array, Array + n1); leftSmaller(Array, n1, RRS1); // หาความต่างสัมบูรณ์สูงสุดระหว่าง LS1 & RRS1 // ใน reversed array right smaller สำหรับ Array[i] คือ // เก็บที่ RRS1[n1-i-1] int result1 = -1; for (int i=0 ; i< n1 ; i++) result1 = max(result1, abs(LS1[i] - RRS1[n1-1-i])); // คืนค่าความต่างสูงสุดระหว่าง LS1 & RRS1 return result1; } // โปรแกรมหลัก 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
