/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public int[] nextLargerNodes(ListNode head) { List<Integer> L = new ArrayList<>(); for(;head!=null;head=head.next) { L.add(head.val); } int []result=new int[L.size()]; Stack<Integer> stack = new Stack<>(); for(int i=0;i<L.size();++i) { while(!stack.isEmpty()&&L.get(stack.peek())<L.get(i)) { result[stack.pop()]=L.get(i); } stack.push(i); } return result; } }
最开始直接用暴力解法accept了。。耗时1秒多点, 用stack解法只要39ms。
但是暴力解法只要不停的循环去搜索就行,不需要额外空间,stack方法需要至少O(n)空间,stack用多少不好说, 所以应该是在O(n)到2*O(n)之间。
最坏情况,整个list是标准的从大到小的顺序,这时候就变成了stack一直增加,保存了几乎整个数组,然后int数组利用默认的0值直接返回。