Untitled

mail@pastecode.io avatarunknown
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))