Next Greater Element II trong C++

Cho mảng vòng (phần tử sau cuối là phần tử đầu). Với mỗi phần tử, tìm Next Greater Number: phần tử đầu tiên lớn hơn nó khi duyệt theo chiều kim đồng hồ (có thể vòng lại đầu). Nếu không có thì -1.

Ví dụ: [1,2,1,3,2,1] → [2,3,3,-1,3,2].

Giải thuật (Monotonic Stack + Circular)

• n = nums.size(), res size n điền -1, stack st lưu chỉ số.
• Duyệt i = 0 .. 2n-1:
  • idx = i % n, x = nums[idx].
  • Khi st không rỗng và nums[st.top()] < x:
    • res[st.top()] = x, st.pop().
  • st.push(idx).
• Trả về res.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

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;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,2,1,3,2,1};
    for (int x : ob.nextGreaterElements(v)) cout << x << " ";
    return 0;
}

Input

[1,2,1,3,2,1]

Output

2 3 3 -1 3 2