Code & Func

今天的题目是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)，虽然说第二种方法只需要扫描一遍，但是因为它栈中需要保存元素的值和元素的下标，所以在一些情况下估计跑的还不如第一种方法。