Code & Func
2020-10-10

今天的题目是1019. Next Greater Node In Linked List

这种求下一个更大的元素用单调栈就可以解决了。

简单来讲,就是从后往前遍历,每次都将当前元素压入栈中,并且压栈前确定当前元素的下一个更大的元素。确认下一个更大的元素的方式是,检查栈顶元素是否大于当前元素,如果不大于,则弹出栈顶元素,并继续检查直到找到或者栈空。

由于题目给出的是链表,而我们又需要从后往前遍历,所以先遍历一次链表得到元素数组,而且因为可以重用这个数组作为返回值,所以消耗的空间并没有增加

1
vector<int> nextLargerNodes(ListNode* head) {
2
vector<int> val;
3
while (head)
4
{
5
val.push_back(head->val);
6
head = head->next;
7
}
8
stack<int> st;
9
int temp;
10
for(int i = val.size() - 1;i>=0;i--) {
11
while (!st.empty() && val[i] >= st.top())
12
{
13
st.pop();
14
}
15
temp = st.empty() ? 0 : st.top();
5 collapsed lines
16
st.push(val[i]);
17
val[i] = temp;
18
}
19
return val;
20
}

上面那种方法需要两边遍历,而之所以需要两次遍历的原因是,在第二次遍历中,我们需要从后向前遍历来实现单调栈,进而需要通过第一次遍历来生成元素数组。 而如果我们可以将从后向前改成从前向后的话,就可以将两次遍历转成一次遍历了。

从前向后遍历链表时,我们可以先假设后面没有元素大于当前元素,所以先在返回值数组对应位置设置0,然后不断判断当前元素是否比栈顶元素要大, 如果比它大的话,那么栈顶元素对应的下一个更大的元素就是当前元素,这时就可以将栈顶元素弹出栈,然后重新比较栈顶元素和当前元素的大小,直到栈空或者当前元素小于栈顶元素。比较完成后,我们将当前元素和其下标压入栈中。 这时,栈中的元素都是还未确定下一个更大的元素,而已经弹出栈的元素都已经确定了下一个更大的元素,当遍历完链表时,就求解出结果了。

代码如下:

1
vector<int> nextLargerNodes(ListNode* head) {
2
vector<int> val;
3
while (head)
4
{
5
val.push_back(head->val);
6
head = head->next;
7
}
8
stack<int> st;
9
int temp;
10
for(int i = val.size() - 1;i>=0;i--) {
11
while (!st.empty() && val[i] >= st.top())
12
{
13
st.pop();
14
}
15
temp = st.empty() ? 0 : st.top();
5 collapsed lines
16
st.push(val[i]);
17
val[i] = temp;
18
}
19
return val;
20
}

以上两种方法的时间复杂度和空间复杂度都是O(n),虽然说第二种方法只需要扫描一遍,但是因为它栈中需要保存元素的值和元素的下标,所以在一些情况下估计跑的还不如第一种方法。

上一条动态