21. Stack push pop-up sequence

There are two solutions: (there is another point of attention in this problem. When obtaining the subscript according to the value, you cannot use the Arrays.binarySearch() method. Because this method is only valid for ordered arrays.)

Solution 1: mathematical derivation. Find the position index of the first number in popA in pushA. The numbers before index must appear in the opposite order in popA.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
        for(int j=0;j<popA.length;j++){
            map.put(popA[j],j);
        }
        int index=0;
        for(int k=0;k<pushA.length;k++){
            index=k;
            if(pushA[k]==popA[0]){
                break;
            }
        }
        for(int l=0;l<pushA.length;l++){
            if(!map.containsKey(pushA[l]))
                return false;
        }
        for(int i=0;i<index-1;i++){
            if(map.get(pushA[i])<map.get(pushA[i+1])){
                return false;
            }
        }
        return true;
    }
}

Solution 2: program simulation, build a stack. Before meeting popA[0], push the elements in pushA to the stack, and then traverse popA once. When the elements traversed are the same as the elements on the top of the stack, stack will pop once. Finally, check whether the stack is empty.

import java.util.ArrayList;
import java.util.Stack;
public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stk = new Stack<Integer>();
        int lenA=pushA.length;
        int lenB=popA.length;
        if(null==pushA||null==popA||0==lenA||0==lenB||lenA!=lenB)
            return false;
        for(int i=0;i<lenA;i++)
        {
            stk.push(pushA[i]);
            if(pushA[i]==popA[0])
                break;
        }
        for(int j=0;j<lenB;j++)
        {
            if(popA[j]!=stk.peek())
                continue;
            if(popA[j]==stk.peek())
            {
                stk.pop();
            }
        }
        return stk.isEmpty();
    }
}

 

Tags: Java

Posted on Sat, 02 Nov 2019 11:01:28 -0700 by tom_b