题目描述
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.
Input: [2,1,5]
Output: [5,5,0]
题意:求数组中每一个元素右边第一个比自己大的数。
算法1
题解:典型的单调栈问题,维护一个单调递减的栈,栈中存储的是该元素在数组中的下标。每读入一个数,先将所有小于该数的栈中元素出栈,同时这个数也是右边第一个大于等于这些栈中元素的数。然后将该数下标入栈。
Input: f[2,7,4,3,5]
Output: [7,0,5,5,0]下列栈右边为栈定元素
2:stack:[0]
7:stack:[1] f[0] < 7,res[0] = 7,出栈,将7的下标1入栈
4:stack:[1,2] f[1] > 4,将4的下标2入栈
3:stack:[1,2,3] f[3] > 3,将3的下标3入栈
5:stack:[1,4] f[3] < 5,res[3] = 5,出栈;f[2] < 5,res[2] = 5,出栈;5的下标4入栈。
栈中元素没有右边比这个元素大的数
C++ 代码
vector<int> nextLargerNodes(ListNode* head) {
vector<int> f(10001);
int length = 0;
while(head){f[length++] = head->val;head = head->next;}
vector<int> res(length,0);
stack<int> st;
for(int i = 0 ; i <= length ; i ++)
{
while(!st.empty() && f[i] > f[st.top()])
{
res[st.top()] = f[i];
st.pop();
}
st.push(i);
}
return res;
}