[Rust] O(N log N) using BTreeSet
Approach\n Describe your approach to solving the problem. \nFor more efficient $O(N)$ solution using double stacks, please refer to lee215\'s post.\nThe code be
# Approach\n<!-- Describe your approach to solving the problem. -->\nFor more efficient $O(N)$ solution using double stacks, please refer to [lee215\'s post](https://leetcode.com/problems/next-greater-element-iv/solutions/2756668/java-c-python-one-pass-stack-solution-o-n).\nThe code below inserts indices in non-increasing order of `nums[i]` into `BTreeSet` and for each `i`, literally looks for second next index to `i` in the set.\nOne caveat is, since there might be ties in `nums`, we must use **stable sort** to determine the order of indices. Specifically, the contents of the set when we look at index `i` in the loop is $\\{j\\ |\\ nums[j] > nums[i]\\} \\cup \\{j\\ |\\ nums[j] = nums[i]\\ \\wedge\\ j < i\\}$, so we don\'t mistakenly count tie values as being larger.\n\n# Complexity\n- Time complexity: $O(N \\log N)$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $O(N)$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nuse std::collections::BTreeSet;\nuse std::ops::Bound;\n\nimpl Solution {\n    pub fn second_greater_element(nums: Vec<i32>) -> Vec<i32> {\n        let n = nums.len();\n        let mut order = (0..n).collect::<Vec<_>>();\n        order.sort_by_key(|&i| -nums[i]);\n\n        let mut ans = vec![-1; n];\n        let mut indices = BTreeSet::new();\n        for i in order {\n            for (k, &j) in indices.range((Bound::Excluded(&i), Bound::Unbounded)).enumerate() {\n                if k == 1 {\n                    ans[i] = nums[j];\n                    break;  // important!\n                }\n            }\n            indices.insert(i);\n        }\n        ans\n    }\n}\n```
['Rust']