1019 Next Greater Node in Linked List

这个让我想到了使用单调栈的方法，进行处理，可以实现一边遍历就可以得到结果。

使用单调递减栈保存下标

单调栈和单调队列

• 单调栈和单调队列详解：https://endlesslethe.com/monotone-queue-and-stack-tutorial.html
• 单调栈，顾名思义就是栈内的元素保持一定的单调性的栈，这里的单调递增和单调递减都是从栈顶到栈尾的单调性
• 单调栈和单调队列和正常的栈以及队列使用上是相同的，单调栈满足的是后进先出，单调队列满足的是先进先出。

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def nextLargerNodes(self, head):
        """
        :type head: ListNode
        :rtype: List[int]
        """
        nums = []
        while head:
            nums.append(head.val)
            head = head.next
        stack = []
        res = [0] * len(nums)
        for i, n in enumerate(nums):
            while stack and nums[stack[-1]] < n:
                res[stack.pop()] = n
            stack.append(i)
        return res

Java

Java 代码写的很臭 需要多改 多练

 import java.util.Vector;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] nextLargerNodes(ListNode head) {
        Vector<Integer> vt = new Vector<Integer>();
        ListNode curr = head;
        while(curr != null){
            vt.add(new Integer(curr.val));
            curr = curr.next;
        }
        Stack<Integer> stack = new Stack<Integer>();
        int[] res = new int[vt.size()];
        for(int i = 0; i < vt.size(); i ++){
            int n = vt.get(i).intValue();
            System.out.println(n);
            while(!stack.empty() && vt.get(stack.peek().intValue()).intValue() < n){
                res[stack.pop().intValue()] = n;
            } 
            stack.push(new Integer(i));
        }
        return res;
    }
}