Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2454.html
2454. Next Greater Element IV
- Difficulty: Hard.
- Related Topics: Array, Binary Search, Stack, Sorting, Heap (Priority Queue), Monotonic Stack.
- Similar Questions: Next Greater Element I, Replace Elements with Greatest Element on Right Side.
Problem
You are given a 0-indexed array of non-negative integers nums
. For each integer in nums
, you must find its respective second greater integer.
The second greater integer of nums[i]
is nums[j]
such that:
-
j > i
-
nums[j] > nums[i]
-
There exists exactly one index
k
such thatnums[k] > nums[i]
andi < k < j
.
If there is no such nums[j]
, the second greater integer is considered to be -1
.
- For example, in the array
[1, 2, 4, 3]
, the second greater integer of1
is4
,2
is3
, and that of3
and4
is-1
.
Return** an integer array answer
, where answer[i]
is the second greater integer of nums[i]
.**
Example 1:
Input: nums = [2,4,0,9,6]
Output: [9,6,6,-1,-1]
Explanation:
0th index: 4 is the first integer greater than 2, and 9 is the second integer greater than 2, to the right of 2.
1st index: 9 is the first, and 6 is the second integer greater than 4, to the right of 4.
2nd index: 9 is the first, and 6 is the second integer greater than 0, to the right of 0.
3rd index: There is no integer greater than 9 to its right, so the second greater integer is considered to be -1.
4th index: There is no integer greater than 6 to its right, so the second greater integer is considered to be -1.
Thus, we return [9,6,6,-1,-1].
Example 2:
Input: nums = [3,3]
Output: [-1,-1]
Explanation:
We return [-1,-1] since neither integer has any integer greater than it.
Constraints:
-
1 <= nums.length <= 105
-
0 <= nums[i] <= 109
Solution (Java, C++, Python)
-
class Solution { public int[] secondGreaterElement(int[] nums) { Deque<Integer> stk = new ArrayDeque<>(); PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[0] - b[0]); int n = nums.length; int[] ans = new int[n]; Arrays.fill(ans, -1); for (int i = 0; i < n; ++i) { int v = nums[i]; while (!q.isEmpty() && q.peek()[0] < v) { ans[q.peek()[1]] = v; q.poll(); } while (!stk.isEmpty() && nums[stk.peek()] < v) { q.offer(new int[] {nums[stk.peek()], stk.pop()}); } stk.push(i); } return ans; } }
-
using pii = pair<int, int>; class Solution { public: vector<int> secondGreaterElement(vector<int>& nums) { stack<int> stk; priority_queue<pii, vector<pii>, greater<pii>> q; int n = nums.size(); vector<int> ans(n, -1); for (int i = 0; i < n; ++i) { int v = nums[i]; while (!q.empty() && q.top().first < v) { ans[q.top().second] = v; q.pop(); } while (!stk.empty() && nums[stk.top()] < v) { q.push({nums[stk.top()], stk.top()}); stk.pop(); } stk.push(i); } return ans; } };
-
class Solution: def secondGreaterElement(self, nums: List[int]) -> List[int]: stk = [] q = [] ans = [-1] * len(nums) for i, v in enumerate(nums): while q and q[0][0] < v: ans[q[0][1]] = v heappop(q) while stk and nums[stk[-1]] < v: heappush(q, (nums[stk[-1]], stk.pop())) stk.append(i) return ans
-
func secondGreaterElement(nums []int) []int { stk := []int{} q := hp{} n := len(nums) ans := make([]int, n) for i := range ans { ans[i] = -1 } for i, v := range nums { for len(q) > 0 && q[0].v < v { ans[q[0].i] = v heap.Pop(&q) } for len(stk) > 0 && nums[stk[len(stk)-1]] < v { heap.Push(&q, pair{nums[stk[len(stk)-1]], stk[len(stk)-1]}) stk = stk[:len(stk)-1] } stk = append(stk, i) } return ans } type pair struct{ v, i int } type hp []pair func (h hp) Len() int { return len(h) } func (h hp) Less(i, j int) bool { a, b := h[i], h[j] return a.v < b.v } func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) } func (h *hp) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).