广州做网站优化,怎么建php网站,淮安市做网站,做跨境的网站通过万岁#xff01;#xff01;#xff01;
题目#xff1a;给你一个链表#xff0c;然后让你从链表中移除一些节点#xff0c;移除的规则就是我们选择的这个节点在原链表中往右不能有比这个节点大的值。思路#xff1a;这个题我最开始以为是双指针#xff0c;然后找…通过万岁
题目给你一个链表然后让你从链表中移除一些节点移除的规则就是我们选择的这个节点在原链表中往右不能有比这个节点大的值。思路这个题我最开始以为是双指针然后找最大值就好了。其实如果给的是数组的话双指针的方法也应该是可以的。但是他给的是一个链表我们就不太好通过index处理了。其实问题的关键就是我们找到一个地方以后如何倒推处理前面的。想到倒退我们其实可以考虑到栈了。我们将满足的条件的元素进行入栈也就是说栈内的元素就是临时想要的链表但是如果我们当前遍历的节点大于栈顶元素那么栈顶元素就不是我们要找的元素这时候就要将栈顶元素出栈栈顶元素会一直出栈直到栈顶元素的值大于当前节点或者栈顶元素为空我们就把当前元素入栈。其实还存在一个问题就是我们最后如何将栈顶元素构建成一个list。这个问题其实我们只要用ret标记栈底元素然后每次加入元素的时候都让栈顶元素指向这个元素就好了。如果栈是空的则直接让ret指向这个元素就好了。最后返回ret。这样就ok了。但是我不太清楚为啥这个思路的时间复杂度不太好。技巧栈
class Solution {public ListNode removeNodes(ListNode head) {if (head null || head.next null) {return head;}ListNode ret head;StackListNode stack new Stack();while (head ! null) {if (stack.isEmpty()) {stack.push(head);ret head;} else {while (!stack.isEmpty() stack.peek().val head.val) {stack.pop();}if (!stack.isEmpty()) {stack.peek().next head;} else {ret head;}stack.push(head);}head head.next;}return ret;}
}总结这个题还是比较有意思的里面的小点也是比较多的。主要是如何考虑到用栈来解决这个问题这一步感觉还是比较关键的剩下的地方都是锦上添花了。
