โจทย์: Next Greater Element II (Circular Array)
ให้อาร์เรย์ วน (circular) (องค์ประกอบสุดท้ายเชื่อมกับองค์ประกอบแรก) ต้องหา Next Greater Element** สำหรับแต่ละองค์ประกอบ Next Greater ของ x คือ องค์ประกอบแรกที่ มากกว่า x เมื่อเดินไปข้างหน้า (รวมถึงวนกลับมาหน้า) หากไม่มี → -1
ตัวอย่าง: nums = [1, 2, 1, 3, 2, 1]
Index 0 (1): ถัดไปคือ 2 → 2
Index 1 (2): ถัดไปคือ 1,3 → 3
Index 2 (1): ถัดไปคือ 3 → 3
Index 3 (3): ไม่มีตัวไหนมากกว่า 3 → -1
Index 4 (2): วนกลับหา 1,1,2,3 → 3
Index 5 (1): วนกลับหา 1,2 → 2
ผลลัพธ์: [2, 3, 3, -1, 3, 2]
อัลกอริทึม: Monotonic Stack + Circular Traversal
- สร้างผลลัพธ์
resขนาด n เติม -1 - ใช้ stack เก็บ index** ขององค์ประกอบที่ยังไม่เจอ next greater
- วนลูป
iจาก 0 ถึง2n - 1(วน 2 รอบเพื่อจำลอง circular):idx = i % n(index จริงในอาร์เรย์)x = nums[idx]- ในขณะที่ stack ไม่ว่าง และ
nums[stack.top()] < x:res[stack.top()] = x(เจอ next greater แล้ว)stack.pop()
stack.push(idx)
- ส่งคืน
res
การวน 2 รอบรับประกันว่าทุกตัวได้โอกาส "มอง" ครบทุกตัวอื่น รอบที่ 2 จะ resolve ตัวที่ไม่เจอในรอบแรก
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v) {
cout << "[";
for (int i = 0; i < v.size(); i++) {
cout << v[i];
if (i + 1 < v.size()) cout << ", ";
}
cout << "]" << endl;
}
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, -1);
stack<int> st; // เก็บ index
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};
print_vector(ob.nextGreaterElements(v));
return 0;
}
Input
[1,2,1,3,2,1]
Output
[2, 3, 3, -1, 3, 2]
ความซับซ้อน (Complexity)
- เวลา: O(n) - แต่ละ index push/pop สูงสุด 1 ครั้งต่อรอบ (2 รอบ = O(2n) = O(n))
- พื้นที่: O(n) - stack + result
