1019. Next Greater Node In Linked List

LeetCode
, ,

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

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

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

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

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

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

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

代码如下：

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

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