องค์ประกอบที่เล็กกว่าถัดไปใน C++

องค์ประกอบที่เล็กกว่าตัวถัดไปคือองค์ประกอบที่เป็นองค์ประกอบที่เล็กกว่าตัวแรกหลังจากนั้น มาดูตัวอย่างกัน

arr =[1, 2, 3, 5, 4]

องค์ประกอบที่เล็กกว่าถัดไปสำหรับ 5 คือ 4 และองค์ประกอบที่เล็กกว่าถัดไปสำหรับองค์ประกอบ 1, 2, 3 คือ -1 เนื่องจากไม่มีองค์ประกอบที่เล็กกว่าหลังจากนั้น

อัลกอริทึม

• เริ่มต้นอาร์เรย์ด้วยตัวเลขสุ่ม

• เริ่มต้นสแตก

• เพิ่มองค์ประกอบแรกลงในสแต็ก

• วนซ้ำองค์ประกอบของอาร์เรย์

  • หากสแต็กว่างเปล่า ให้เพิ่มองค์ประกอบปัจจุบันลงในสแต็ก

  • ในขณะที่องค์ประกอบปัจจุบันมีขนาดเล็กกว่าองค์ประกอบด้านบนของสแต็ก

    • พิมพ์องค์ประกอบด้านบนที่มีองค์ประกอบที่เล็กกว่าถัดไปเป็นองค์ประกอบปัจจุบัน

    • เปิดองค์ประกอบด้านบน

  • เพิ่มองค์ประกอบลงในสแต็ก

• ในขณะที่สแต็กไม่ว่างเปล่า

  • พิมพ์องค์ประกอบที่มีองค์ประกอบที่เล็กกว่าถัดไปเป็น -1

การนำไปใช้

ต่อไปนี้เป็นการนำอัลกอริธึมข้างต้นไปใช้ใน C++

#include <bits/stdc++.h>
using namespace std;
void nextSmallerElements(int arr[], int n) {
   stack<int> s;
   s.push(arr[0]);
   for (int i = 1; i < n; i++) {
      if (s.empty()) {
         s.push(arr[i]);
         continue;
      }
      while (!s.empty() && s.top() > arr[i]) {
         cout << s.top() << " -> " << arr[i] << endl;
         s.pop();
      }
      s.push(arr[i]);
   }
   while (!s.empty()) {
      cout << s.top() << " -> " << -1 << endl;
      s.pop();
   }
}
int main() {
   int arr[] = { 5, 4, 3, 2, 1 };
   int n = 5;
   nextSmallerElements(arr, n);
   return 0;
}

ผลลัพธ์

หากคุณเรียกใช้โค้ดด้านบน คุณจะได้ผลลัพธ์ดังต่อไปนี้

1 -> 2
2 -> 3
3 -> 4
4 -> 5
5 -> -1