最大元素。算法

Question

我正试图从hackerrank解决最大元素任务。任务link 想法是通过链接列表实现堆栈，其中一个额外的字段在最大节点中。它有时工作得很好，但在更大的例子中，我的节点得到错误的最大元素。我做错了什么 ？

public class Stack 
{ 
public class Node 
{ 
    long data; 
    long max; 
    Node next; 
} 

Node head = null; 

public void push(long data) 
{ 
    if(head == null) 
    { 
     head = new Node(); 
     head.next = null; 
     head.data = data; 
     head.max = data; 
     return; 
    } 

    Node current = head; 

    while(current.next != null) 
     current = current.next; 

    Node temp = new Node(); 
    temp.next = null; 
    temp.data = data; 
    if(current.data > temp.data) 
    { 
     temp.max = current.data; 
    }else 
    { 
     temp.max = data; 
    } 

    current.next = temp; 
} 

public void pop() 
{ 
    if(head == null) 
     return; 

    if(head.next == null) 
    { 
     head = null; 
     return; 
    } 

    Node current = head; 

    while(current.next.next != null) 
     current = current.next; 

    current.next = null; 
} 
public long getMax() 
{ 
    if(head == null) 
     return -1; 

    Node current = head; 

    while(current.next != null) 
     current = current.next; 

    return current.max; 
} 
} 

Answer 1

你正在做推错比较以下行

if(current.data > temp.data) { temp.max = current.data; }else { temp.max = data; } 

它必须是

if(current.max > temp.data) { temp.max = current.max; }else { temp.max = data; } 

在这里，你必须检查与当前最大值推值如果新的更大，那么它是最大的。否则当前最大值在推送节点中仍然保留其最大值贪婪