1019.链表中的下一个更大元素

下面是题目

下面是题目给出的模板

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
     vector<int> nextLargerNodes(ListNode* head) {
   
     }
};

• 这里用最普通的思路，和用栈模拟的方法

//这个思路就时很简单，用两个迭代器，每次更新一个迭代器，都把他们后面的所有元素遍历一遍
class Solution {
public:
      vector<int> nextLargerNodes(ListNode* head) {
          ListNode*cur1 = head;
          vector<int>v;
          while(cur1->next)
          {
            ListNode *cur2 = cur1->next;
            while(cur2)
            {
                if(cur2->val>cur1->val)
                {
                    v.push_back(cur2->val);
                    break;
                }
                cur2=cur2->next;
            }
            if(!cur2)
                    v.push_back(0);
            cur1 = cur1->next;
          }
        v.push_back(0);
          return v;
    }
};

用栈来做，思维要求比较高

vector<int> nextLargerNodes(ListNode* head) {

        //将链表放入结果数组
        vector<int> res;
        while (head)
        {
            res.push_back(head->val);
            head = head->next;
        }

        stack<int> stack;

        //从右往左遍历
        for (int i = (int)res.size() - 1; i >= 0; --i)
        {
            int cur = res.at(i); //先暂存当前元素
            while (!stack.empty() && cur >= stack.top()) 
            //注意: 等于号不能少 等于时也需要出栈 这里是找严格大于的数
            {
                stack.pop();  //淘汰小的 留下更大的
            }
            res.at(i) = (stack.empty() ? 0 : stack.top()); 
            //栈空 右边没有更大的
            stack.push(cur);
        }
        return res;
    }
};
 //我们不妨拿一组数据来模拟一下 2 7 2 3  
/*
1： res[3]= 3 ，cur = 3 ， stack 内的元素 ：0 =>>>>> res[3]=0 stack 内的元素: 3
2： res[2]= 2 ，cur = 2 ， stack 内的元素 ：3 =>>>>> res[2]=3 stack 内的元素: 3
3： res[1]= 7 ，cur = 7 ， stack 内的元素 ：3 =>>>>> stack 出栈res[1]=0 stack 内的元素:7
4： res[0]= 2 ，cur = 2 ， stack 内的元素 ：7 =>>>>> res[0]=7 stack 内的元素: 7
然后输出
*/