สมมติว่าเรามีอาร์เรย์แบบวงกลม (องค์ประกอบถัดไปขององค์ประกอบสุดท้ายคือองค์ประกอบแรกของอาร์เรย์) เราต้องแสดงจำนวนที่มากกว่าถัดไปสำหรับทุกองค์ประกอบ ในที่นี้ จำนวนที่มากกว่าเดิมของจำนวน x เป็นจำนวนที่มากกว่าตัวแรกของลำดับการเคลื่อนที่ถัดไปในอาร์เรย์ ซึ่งหมายความว่าเราสามารถค้นหาแบบวงกลมเพื่อหาจำนวนที่มากกว่าถัดไป หากไม่มีอยู่ ก็จะเป็น -1 ดังนั้นหากตัวเลขเป็น [1, 2, 1, 3, 2, 1] ผลลัพธ์จะเป็น:[2,3,3,-1,3,2]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- n :=ขนาดของอาร์เรย์
- กำหนดหนึ่งอาร์เรย์ที่เรียกว่า res ขนาด n และเติมด้วย -1 กำหนดหนึ่งสแต็ก st
- สำหรับฉันอยู่ในช่วง 0 ถึง 2n
- ดัชนี :=ฉัน mod n, x :=nums[ดัชนี]
- ในขณะที่ st ไม่ว่างเปล่าและ nums[top of stack]
- res[บนสุดของสแต็ก] :=x
- ลบองค์ประกอบด้านบนออกจากสแต็ก
- แทรกดัชนีลงในสแต็ก
ตัวอย่าง(C++)
ให้เราดูการใช้งานต่อไปนี้เพื่อทำความเข้าใจ −
#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> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector <int> res(n, - 1);
stack <int> st;
for(int i = 0; i < 2 * n; i++){
int idx = i % n;
int x = nums[idx];
while(!st.empty() && nums[st.top()] < x){
res[st.top()] = x;
st.pop();
}
st.push(idx);
}
return res;
}
};
main(){
Solution ob;
vector<int> v = {1,2,1,3,2,1};
print_vector(ob.nextGreaterElements(v));
} อินพุต
[1,2,1,3,2,1]
ผลลัพธ์
[2,3,3,-1,3,2]
