Làm thế nào để tìm giá trị số nguyên tối đa trong ngăn xếp mà không sử dụng tối đa() hoặc lặp qua nó?

Question

Tôi được hỏi trong một cuộc phỏng vấn câu hỏi sau đây: nếu bạn có một Stack of Integers, bạn sẽ tìm thấy giá trị tối đa của Stack mà không sử dụng Collections.max và không lặp qua Stack và so sánh các phần tử. Tôi đã trả lời bằng mã dưới đây vì tôi không biết cách nào khác ngoài việc sử dụng bất kỳ API Bộ sưu tập nào hoặc lặp qua Stack và sử dụng các so sánh. Bất kỳ ý tưởng?

import java.util.Collections; 
import java.util.Stack; 

public class StackDemo { 
    public static void main(String[] args){ 
     Stack lifo = new Stack(); 
     lifo.push(new Integer(4)); 
     lifo.push(new Integer(1)); 
     lifo.push(new Integer(150)); 
     lifo.push(new Integer(40)); 
     lifo.push(new Integer(0)); 
     lifo.push(new Integer(60)); 
     lifo.push(new Integer(47)); 
     lifo.push(new Integer(104)); 

     if(!lifo.isEmpty()){ 
      Object max = Collections.max(lifo); 
      System.out.println("max=" + max.toString()); 
     } 
    } 
} 

Answer 1

Edit:

mà không iterating trên Stack

không thực sự cấm tất cả lặp. Thay vào đó, câu hỏi chỉ cấm thực hiện đơn giản

for (Integer i : lifo) 

Do đó, giải pháp này đáp ứng các giới hạn của câu hỏi.

---

Chỉ cần bỏ trống một bản sao của chồng. bật từng phần tử từ bản sao, kiểm tra tối đa đối với một số nguyên trong một khoảng thời gian.

Stack<Integer> lifoCopy = (Stack<Integer>) lifo.clone(); 
int max = Integer.MIN_VALUE; 

while (!lifoCopy.isEmpty()) 
{ 
    max = Math.max(lifoCopy.pop(), max); 
} 

System.out.println("max=" + max.toString()); 

Điều này sẽ làm việc cho bạn trong thời gian O (n) ngay cả khi người phỏng vấn quyết định hạn chế hơn và không cho phép nhiều chức năng được tích hợp sẵn (tối đa, tối thiểu, vv ..).

Ngoài ra, nếu bạn cần phải có hề hấn gì ban đầu, nhưng không thể sử dụng bản sao, bạn có thể làm như vậy với một ngăn xếp thêm:

Stack<Integer> reverseLifo = new Stack<Integer>(); 
int max = Integer.MIN_VALUE; 

while (!lifo.isEmpty()) 
{ 
    int val = lifo.pop(); 

    max = Math.max(val, max); 

    reverseLifo.push(val); 
} 

while (!reverseLifo.isEmpty()) 
{ 
    lifo.push(reverseLifo.pop()); 
} 

System.out.println("max=" + max.toString()); 

Cuối cùng, điều này giả định rằng so sánh với một biến temp là chấp nhận được . Nếu không có phép so sánh nào cả, thì giải pháp này kết hợp với this method sẽ hoạt động.

Answer 2

Khi bạn đẩy các yếu tố vào ngăn xếp, cập nhật giá trị max

void main() 
    int max = Integer.min 
    lifo.push(1) 

khi

void push(Integer value) { 
     //push into stack 
     //update max value 
    } 

Answer 3

Bạn có thể chuyển nó sang một TreeSet với:

int myMax = new TreeSet<Integer>(lifo).last(); 

Answer 4

Sử dụng Bộ sưu tập. sắp xếp với một Trình so sánh sắp xếp theo thứ tự giảm dần và sau đó xem phần tử trên cùng từ Ngăn xếp.

Answer 5

Bằng cách sử dụng Collections.min() thay vì:

if (!lifo.isEmpty()) { 
    Integer max = Collections.min(lifo, new Comparator<Integer>() { 
    @Override 
    public int compare(Integer o1, Integer o2) { 
     return o2.compareTo(o1); 
    } 
    }); 
    System.out.println("max=" + max.toString()); 
} 

Lưu ý rằng tùy chỉnh Comparator flips sự so sánh để Collections.min() thực sự sẽ trở lại tối đa.

Answer 6

Không lặp lại, bạn có thể thực hiện cuộc gọi đệ quy. Nếu nó không phải là bài tập ở nhà thì không hợp lý để làm như vậy. Hoặc cách khác bạn có thể làm điều này mà không cần lặp lại & đệ quy.

Tuy nhiên một cách tiếp cận nhanh chóng n đơn giản là ở đây:

public class StackDemo { 
    public static int max = 0; //set this to least, may be negative 
    public static Stack lifo = new Stack(); 
    public static void main(String[] args){   
     pushToStack(new Integer(4)); 
     pushToStack(new Integer(1)); 

     if(!lifo.isEmpty()){ 
      Object max = Collections.max(lifo); 
      System.out.println("max=" + max); 
     } 
    } 
    void static int pushToStack(Integer value){ 
     lifo.push(value); 
     if(max<value){ 
     max = value; 
     } 
     return max; 
    }  

} 

Answer 7

Không chắc sẽ làm hài lòng này cần câu hỏi của bạn, nhưng việc sử dụng cách này của max() và iteration có thể tránh được, dù sao đi nữa sort không sử dụng iteration và Comparable ở chế độ nền .

if (!lifo.isEmpty()) { 
    Stack sc = (Stack) lifo.clone(); 
    Collections.sort(sc); 
    System.out.println("max=" + sc.get(sc.size() - 1)); 
} 

Answer 8

Bạn có thể sử dụng thay vì bitwise operator ..

public int getMax(int a, int b) 
{ 
    int c = a - b; 
    int k = (c >> 31) & 0x1; 
    int max = a - k * c; 
    return max; 
} 

Bây giờ bạn có thể làm

int max=Integer.MIN_VALUE-1; 
while(!stack.empty()) 
{ 
    max=getMax(max,stack.pop()); 
} 

Answer 9

Điều này có thể được thực hiện trong thời gian O (1) thời gian và O (n) bộ nhớ. Sửa đổi phương thức push và pop (hoặc bằng cách thừa kế mở rộng ngăn xếp chuẩn với chính bạn) để theo dõi giá trị tối đa hiện tại trong một ngăn xếp khác.

Khi bạn đẩy các phần tử vào ngăn xếp của bạn, hãy đẩy tối đa (currentElem, maxStack.peek()) lên maxStack Khi bạn bật các phần tử ra khỏi ngăn xếp, hãy bật tối đa hiện tại từ ngăn xếp tối đa của bạn.

Giải pháp này cho thấy nó tốt, vì vậy tôi sẽ không mở rộng thêm về nó: https://stackoverflow.com/a/3435998/1007845

Answer 10

Mã này:

public static Integer max(Stack stack) { 
    if (stack.isEmpty()) { 
     return Integer.MIN_VALUE; 
    } 
    else { 
     Integer last = (Integer)stack.pop(); 
     Integer next = max(stack); 
     stack.push(last); 
     if (last > next) { 
      return last; 
     } 
     else { 
      return next; 
     }    
    } 
} 

public static void main(String[] args){ 
    Stack lifo = new Stack(); 
    lifo.push(new Integer(4)); 
    lifo.push(new Integer(1)); 
    lifo.push(new Integer(150)); 
    lifo.push(new Integer(40)); 
    lifo.push(new Integer(0)); 
    lifo.push(new Integer(60)); 
    lifo.push(new Integer(47)); 
    lifo.push(new Integer(104)); 

    System.out.println(Arrays.deepToString(lifo.toArray())); 
    System.out.println(max(lifo)); 
    System.out.println(Arrays.deepToString(lifo.toArray())); 
} 

kết quả đầu ra:

[4, 1, 150, 40, 0, 60, 47, 104] 
150 
[4, 1, 150, 40, 0, 60, 47, 104] 

Nó là một đệ quy trên cho chồng, tìm phần tử tối đa và không thay đổi thứ tự ngăn xếp.

Tuy nhiên, lần lặp lại khác với đệ quy chỉ khi bạn define it like that. Ngoài ra, để tìm tối đa bạn phải so sánh tất cả các phần tử bằng cách nào đó - ở bất kỳ dạng toán học nào, với các toán tử quan hệ hoặc bitwise như Anirudh showed. IMHO, khá mơ hồ được xác định nhiệm vụ.

Answer 11

Thời gian để suy nghĩ bên ngoài hộp. Sử dụng các Wolfram Alpha REST API, và yêu cầu sẽ được tính toán kết quả của:

"maximum of " + Arrays.deepToString(lifo.toArray()) 

Nó sẽ return 150.

Answer 12

import java.util.Collections; 
import java.util.Stack; 

public class StackDemo { 
    public static void main(String[] args) { 
     Stack lifo = new Stack(); 
     lifo.push(new Integer(4)); 
     lifo.push(new Integer(1)); 
     lifo.push(new Integer(150)); 
     lifo.push(new Integer(40)); 
     lifo.push(new Integer(0)); 
     lifo.push(new Integer(60)); 
     lifo.push(new Integer(47)); 
     lifo.push(new Integer(104)); 

     System.out.println("max= 150"); // http://xkcd.com/221/ 
    } 
} 

Answer 13

Đây là giải pháp của tôi:

import java.util.Arrays; 
import java.util.Collections; 
import java.util.Stack; 

public class StackDemo { 
    public static void main(String[] args){ 
     Stack lifo = new Stack(); 
     lifo.push(new Integer(4)); 
     lifo.push(new Integer(1)); 
     lifo.push(new Integer(150)); 
     lifo.push(new Integer(40)); 
     lifo.push(new Integer(0)); 
     lifo.push(new Integer(60)); 
     lifo.push(new Integer(47)); 
     lifo.push(new Integer(104)); 

     Object lifoArray[] = lifo.toArray(); 
     Arrays.sort(lifoArray); 
     System.out.println(lifoArray[lifoArray.length-1]); 
    } 
} 

Arrays.sort() xếp thứ thứ tự tăng dần, vì vậy giá trị cuối cùng trong mảng được sắp xếp sẽ là giá trị tối đa.

Answer 14

1 x -Push phần tử x vào ngăn xếp.

2 -Xóa phần tử có ở đầu ngăn xếp.

3 -In phần tử tối đa trong ngăn xếp.

import java.io.*; 
    import java.util.*; 
    import java.text.*; 
    import java.math.*; 
    import java.util.regex.*; 
    public class Solution { 
     public static void main(String[] args) { 
      Scanner sc = new Scanner(System.in); 
      Stack <StackItem> st = new Stack <StackItem>(); 
      int n = sc.nextInt();//number of choice 
      int choice; 
      int max = 0; 
      for (int i = 0; i<n; i++) { 
       choice = sc.nextInt(); 
       if (choice == 1) {//insert/push an item 
        int newInt = sc.nextInt(); 
        if (!st.isEmpty()) { 
         max = st.peek().currentMax; 
        } else { 
         max = 0; 
        } 
        if (newInt > max) { 
         max = newInt; 
        } 
        StackItem item = new StackItem(newInt, max); 
        st.push(item); 
       } else if (choice == 2) {//pop 
        if (!st.isEmpty()) st.pop(); 
       } else if (choice == 3) {//print the maximum item 
        System.out.println(st.peek().currentMax); 
       } 
      } 
     } 
    } 
    class StackItem { 
     int val; 
     int currentMax; 
     StackItem(int val, int max) { 
      this.val = val; 
      this.currentMax = max; 
     } 
    }