สมมติว่ามีลายเซ็นลับที่ประกอบด้วยตัวอักษร 'D' และ 'I' 'D' หมายถึงความสัมพันธ์แบบลดลงระหว่างสองตัวเลข 'I' หมายถึงความสัมพันธ์แบบเพิ่มขึ้นระหว่างสองตัวเลข และลายเซ็นลับนี้ถูกสร้างจากอาร์เรย์จำนวนเต็มพิเศษ ซึ่งมีตัวเลขที่ไม่ซ้ำกันทั้งหมดจาก 1 ถึง n
เช่น ลายเซ็นลับ "DI" สามารถสร้างจากอาร์เรย์แบบ [2,1,3] หรือ [3,1,2] แต่ไม่สามารถสร้างจากอาร์เรย์แบบ [3,2,4] หรือ [2,1,3,4] ซึ่งเป็นการสร้างสตริงพิเศษที่ไม่ถูกต้องที่ไม่สามารถแทนลายเซ็นลับ "DI" ได้
ตอนนี้เราต้องหาการเรียงสับเปลี่ยนที่เล็กที่สุดในระดับเล็กซิโคกราฟิกของ [1, 2, ... n] ที่อาจอ้างถึงลายเซ็นลับที่กำหนดในอินพุต
เช่น ถ้าอินพุทเป็น "DI" ผลลัพธ์จะเป็น [2,1,3] เนื่องจากเรารู้ว่า [3,1,2] สามารถสร้างลายเซ็นลับ "DI" ได้เช่นกัน แต่เนื่องจากเราต้องการหาการเรียงสับเปลี่ยนที่เล็กที่สุดในระดับเล็กซิโคกราฟิก เราจึงต้องส่งออก [2,1,3]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −
กำหนดสแต็ก st
cnt := 2
กำหนดอาร์เรย์ ret
ลูป i := 1 ถึงขนาดของ s ทำ −
ถ้า s[i - 1] เป็น 'D' แล้ว −
แทรก i ลงใน st
แทรก i ที่ท้ายของ ret
ลูป while (st ไม่ว่าง) ทำ −
แทรกค่าบนสุดของ st ที่ท้ายของ ret
ลบสมาชิกออกจาก st
มิฉะนั้น
แทรกขนาดของ s ลงใน st
ลูป while (st ไม่ว่าง) ทำ −
แทรกค่าบนสุดของ st ที่ท้ายของ ret
ลบสมาชิกออกจาก st
คืนค่า ret
ตัวอย่าง
ลองดูการติดตั้งต่อไปนี้เพื่อให้เข้าใจได้ดีขึ้น −
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: vector<int> findPermutation(string s) { stack <int> st; int cnt = 2; vector <int> ret; for(int i = 1; i <= s.size(); i++){ if(s[i - 1] == 'D'){ st.push(i); } else{ ret.push_back(i); while(!st.empty()){ ret.push_back(st.top()); st.pop(); } } } st.push(s.size() + 1); while(!st.empty()){ ret.push_back(st.top()); st.pop(); } return ret; } }; main(){ Solution ob; print_vector(ob.findPermutation("DIID")); } อินพุท
"DIID"
เอาต์พุท
[2, 1, 3, 5, 4, ]
