Leetcode6247-从链表中移除节点

将链表种的元素存到一个数组a中，反向遍历数组a，用另一个s数组记录a中每个元素右侧（包括本身）的最大元素是多少。再顺序遍历数组a中的元素a[i]，如果a[i]==s[i]则说明它的右侧没有比它更大的元素了，于是把a[i]加到链表中即可。

也可以以单调栈来解决数组右侧有无更大元素的问题。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        vector<int> a;
        while(head){
            a.push_back(head->val);
            head=head->next;
        }
        int mx=0;
        vector<int> s(a.size());
        for(int i=a.size()-1;~i;i--){
            if(a[i]>mx){
                mx=a[i];
            }
            s[i]=mx;
        }
        ListNode *h=NULL,*p,*pre=NULL;
        for(int i=0;isize();i++){
            if(a[i]==s[i]){
                p=new ListNode(a[i]);
                if(!h) h=p;
                if(pre) pre->next=p;
                pre=p;
            }
        }
        return h;
    }
};

时间复杂度：O（n）

空间复杂度：O（n）