Giả sử chúng ta có một mảng tròn (phần tử tiếp theo của phần tử cuối cùng là phần tử đầu tiên của mảng), chúng tôi phải hiển thị Số Lớn hơn Tiếp theo cho mọi phần tử. Ở đây Số Lớn hơn Tiếp theo của một số x là số lớn hơn đầu tiên theo thứ tự đi ngang của nó tiếp theo trong mảng, điều này có nghĩa là chúng ta có thể tìm kiếm theo hình tròn để tìm số lớn hơn tiếp theo của nó. Nếu nó không có mặt, thì nó sẽ là -1. Vì vậy, nếu các số là [1, 2, 1, 3, 2, 1], thì đầu ra sẽ là:[2,3,3, -1,3,2]
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- n:=kích thước của mảng
- xác định một mảng được gọi là res, có kích thước n và điền vào mảng này với -1, xác định một ngăn xếp
- cho tôi trong phạm vi 0 đến 2n
- index:=i mod n, x:=nums [index]
- while st không trống và nums [top of stack]
- res [đầu ngăn xếp]:=x
- xóa phần tử trên cùng khỏi ngăn xếp
- chèn chỉ mục vào ngăn xếp
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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));
} Đầu vào
[1,2,1,3,2,1]
Đầu ra
[2,3,3,-1,3,2]