Formatted question description: https://leetcode.ca/all/1019.html
1019. Next Greater Node In Linked List (Medium)
We are given a linked list with head
as the first node. Let's number the nodes in the list: node_1, node_2, node_3, ...
etc.
Each node may have a next larger value: for node_i
, next_larger(node_i)
is the node_j.val
such that j > i
, node_j.val > node_i.val
, and j
is the smallest possible choice. If such a j
does not exist, the next larger value is 0
.
Return an array of integers answer
, where answer[i] = next_larger(node_{i+1})
.
Note that in the example inputs (not outputs) below, arrays such as [2,1,5]
represent the serialization of a linked list with a head node value of 2, second node value of 1, and third node value of 5.
Example 1:
Input: [2,1,5] Output: [5,5,0]
Example 2:
Input: [2,7,4,3,5] Output: [7,0,5,5,0]
Example 3:
Input: [1,7,5,1,9,2,5,1] Output: [7,9,9,9,0,5,0,0]
Note:
1 <= node.val <= 10^9
for each node in the linked list.- The given list has length in the range
[0, 10000]
.
Companies:
Microsoft
Related Topics:
Linked List, Stack
Solution 1. Monostack
// OJ: https://leetcode.com/problems/next-greater-node-in-linked-list/
// Time: O(N)
// Space: O(N)
class Solution {
ListNode *reverseList(ListNode *head) {
ListNode h;
while (head) {
auto node = head;
head = head->next;
node->next = h.next;
h.next = node;
}
return h.next;
}
public:
vector<int> nextLargerNodes(ListNode* head) {
vector<int> ans;
stack<int> s;
head = reverseList(head);
for (; head; head = head->next) {
while (s.size() && s.top() <= head->val) s.pop();
ans.push_back(s.size() ? s.top() : 0);
s.push(head->val);
}
reverse(ans.begin(), ans.end());
return ans;
}
};
Solution 2. Monostack
// OJ: https://leetcode.com/problems/next-greater-node-in-linked-list/
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<int> nextLargerNodes(ListNode* head) {
vector<int> ans;
stack<int> s;
for (; head; head = head->next) ans.push_back(head->val);
for (int i = 0; i < ans.size(); ++i) {
while (s.size() && ans[s.top()] < ans[i]) {
ans[s.top()] = ans[i];
s.pop();
}
s.push(i);
}
for (; s.size(); s.pop()) ans[s.top()] = 0;
return ans;
}
};
Java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] nextLargerNodes(ListNode head) {
Stack<ListNode> nodesStack = new Stack<ListNode>();
ListNode temp = head;
while (temp != null) {
nodesStack.push(temp);
temp = temp.next;
}
int length = nodesStack.size();
int[] nextLarger = new int[length];
Stack<Integer> largestStack = new Stack<Integer>();
for (int i = length - 1; i >= 0; i--) {
ListNode node = nodesStack.pop();
int value = node.val;
while (!largestStack.isEmpty() && largestStack.peek() <= value)
largestStack.pop();
if (!largestStack.isEmpty())
nextLarger[i] = largestStack.peek();
largestStack.push(value);
}
return nextLarger;
}
}