Untitled
plain_text
2 months ago
3.9 kB
1
Indexable
Never
class ListNode { ListNode next; int val; public ListNode(int val) { this.val = val; } public ListNode(int val, ListNode next) { this.val = val; this.next = next; } } public class LongestNonIncreasingSublist { public int[] findLongestList(ListNode head) { ListNode curSublistHead = head, longestHead = head; int longest = head == null ? 0 : 1, curSublistLen = longest; while (head.next != null) { if (head.val >= head.next.val) { ++curSublistLen; }else { if (longest < curSublistLen) { longest = curSublistLen; longestHead = curSublistHead; } curSublistLen = 1; curSublistHead = head.next; } head = head.next; } if (longest < curSublistLen) { longestHead = curSublistHead; longest = curSublistLen; } int[] ans = new int[longest]; for (int i = 0; i < longest; ++i) { ans[i] = longestHead.val; longestHead = longestHead.next; } return ans; } private void assignValues(ListNode dummy, int[] arr) { ListNode cur = dummy; for (int a : arr) { cur.next = new ListNode(a); cur = cur.next; } } public static void main(String[] args) { LongestNonIncreasingSublist lnis = new LongestNonIncreasingSublist(); ListNode dummy = new ListNode(-1); int[] arr = {3,2,1,4}; lnis.assignValues(dummy, arr); System.out.println(Arrays.toString(lnis.findLongestList(dummy.next))); arr = new int[]{3,2,1,4,5,4,3,2,1,0}; lnis.assignValues(dummy, arr); System.out.println(Arrays.toString(lnis.findLongestList(dummy.next))); arr = new int[]{2,5,4,4,5}; lnis.assignValues(dummy, arr); System.out.println(Arrays.toString(lnis.findLongestList(dummy.next))); arr = new int[]{3,2,1,4,3,3,3,2,2,1,1,7,7,7,7,7,6,6,6,6,6,6,5}; lnis.assignValues(dummy, arr); System.out.println(Arrays.toString(lnis.findLongestList(dummy.next))); } } class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next class LongestNonIncreasingSublist: def findLongestList(self, head: ListNode) -> List[int]: longest = cur_sublist_len = 1 if head else 0 cur_sublist_head = longest_head = head while head.next: if head.val >= head.next.val: cur_sublist_len += 1 else: if longest < cur_sublist_len: longest = cur_sublist_len longest_head = cur_sublist_head cur_sublist_head = head.next cur_sublist_len = 1 head = head.next if longest < cur_sublist_len: longest, longest_head = cur_sublist_len, cur_sublist_head ans = [] for i in range(longest): ans.append(longest_head.val) longest_head = longest_head.next return ans def assignValues(self, dummy: ListNode, arr: [int]) -> None: cur = dummy for a in arr: cur.next = ListNode(a) cur = cur.next lnis, dummy = LongestNonIncreasingSublist(), ListNode(-1) arr = [3,2,1,4] lnis.assignValues(dummy, arr) print(lnis.findLongestList(dummy.next)) arr = [3,2,1,4,5,4,3,2,1,0] lnis.assignValues(dummy, arr) print(lnis.findLongestList(dummy.next)) arr = [2,5,4,4,5] lnis.assignValues(dummy, arr) print(lnis.findLongestList(dummy.next)) arr = [3,2,1,4,3,3,3,2,2,1,1,7,7,7,7,7,6,6,6,6,6,6,5] lnis.assignValues(dummy, arr) print(lnis.findLongestList(dummy.next))