经典算法题解析(堆、栈、队列)

1、用两个栈实现队列
用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素

public soluttion(){
    Stack stack1=new Stack<Integer>();
    Stack stack2=new Stack<Integer>();
    public void push(int num){
        stack1.push(num);
    }   
    public void pop(){
        if(stack2==null){
            while(stack1!=0){
                stack2.push(stack1.pop());
            }
        }
        stack2.pop();
    }
}

解析：
队列是先进先出，栈是先进后出。利用两个栈实现队列，放入第二个栈时顺序被置换了，取出元素时即按照队列的顺序

2、包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素

方法一：采用switch判断

public bool isValid(string s) {
    Stack<character> stk = new Stack<>();
    int[] s=s.toCharArrary();
    for(int i=0;i<s.size();i++){
        switch(s[i]){
            case '(':
            case '[':
            case '{':
                //当前字符为'(','{','['时，元素入栈
                stk.push(s[i]);   
                break;
            case ')':       
              //栈空或者括号栈顶字符与当前字符不匹配，则序列为不合法序列 
                if(stk.empty() || stk.top() != '(')   
                    return false;
                //匹配的栈顶元素出栈
                stk.pop();                   
                break;
            case ']':
                if(stk.empty() || stk.top() != '[')
                    return false;
                stk.pop();
                break;
            case '}':
                if(stk.empty() || stk.top() != '{')
                    return false;
                stk.pop();
                break;
        }
    }
    //当括号以正确顺序关闭时则最后的栈为空
    return stk.isEmpty()?true:false;      
}

解析：
判断是否是（{、[、（），若是则依次将其依次放入栈中
判断是否是（}、]、)）,依次从栈中取出查看是否对应
最后的判空，相当于是对边界条件的检查

方法二：采用for判断

public bool isValid(string s) {
    int[character] s=s.toCharArrary(); 
    Stack<character> stk=new Stack<>();
    for(int i=0;i<s.size();i++){
        //当为(字符时，将匹配字符入栈，下同
        if(s[i] == '(')           
            stk.push(')');
        else if(s[i] == '[')
            stk.push(']');
        else if(s[i] == '{')
            stk.push('}');
        else{                
            //当字符不是'(','[','{'这三种字符时，则判断当前字符是否与栈顶元素一样(栈非空时)
            if(stk.isEmpty() || s[i] != stk.top())
                return false;
            stk.pop();
        }
    }
    return stk.isEmpty();
}

解析：
若是（(、{、[），则将其对应的（）、}、]）依次存入栈中，
若是（)、}、]），依次从栈中取出判断是否一样
最后的判空，相当于是对边界条件的检查

3、滑动窗口的最大值
给定一个长度为 n 的数组 num 和滑动窗口的大小 size ，找出所有滑动窗口里数值的最大值
方法一：直接法

public ArrayList<Integer> maxInWindow(int[] nums,int size){
    //边界值情况
    if(size<1||size>nums.length){
        return null;
    }
    int len=nums.length;
    ArrayList<Integer> maxs=new ArrayList<>();
    int left=0;
    int right=size-1;
    //右边最先到达边界
    while(right<len){
        int m=calcMax(left,right,nums);
        maxs.add(m)
        left++;
        right++;
    }
    return maxs;
}   
public int calcMax(int l,int r,int[] nums){
    int max=nums[l];
    while(l<=r){
        if(nums[l]>max) 
            max=nums[l];
        l++;
    }
    return max;
}

解析：
将每一次滑动后的窗口值从左到右依次进行比较，不可避免地进行多次重复的比较，复杂度较高

方法二：列用双端队列

public ArrayList<Integer> maxInWindow(int[] nums,int size){
    //边界值况
    Deque<Integer> deque=new LinkedList<>();
    ArrayList  result=new ArrayList<Integer>();
    //新加元素依次和之前的所有元素做比较，将小的排除，这样就能保证对头元素始终处于最大值
    for(int i=0;i<nums.length,i++){
        while(!deque.isEmpty()&&nums[deque.getLast()]<nums[i]){
            deque.pollLast();   
        }
        //依次添加数组元素
        deque.addLast(i)
        //删除不在移动窗口内的队首元素
        if(deque.isEmpty()&&nums[deque.getFirst()]<=i-size){
            deque.pollFirst();
        }
        //将每一次移动窗口的最大值添加进结果集
        if(i>=size-1){
            result.add(num[deque.getFirst()]);
        }
    }
    return result;
}

4、最小的K个数
给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)

方法一：sort排序法

public ArrayList<Integer> getLeastNums(int[] arr,int k){
    ArrayList<Integer> res = new ArrayList<Integer>();
    //排除特殊情况
    if(k == 0 || arr.length == 0) 
        return res;
    //排序
    Arrays.sort(arr); 
    //因为k<=input.length,取前k小
    for(int i = 0; i < k; i++){ 
        res.add(input[i]);
    }
    return res;
}

解析：
使用官方内置方法排好序，将前K个数放入集合中即可

方法二：堆排序

public ArrayList<Integer> getLeastNums(int[] arr,int k){
    ArrayList res=new ArrayList<Integer>();
    //边界情况排除
    if(arr.length<=0||k==0){
        return res;
    }
    PriorityQueue<Integer> q=new priorityQueue<>((o1,o2)->o2.compareTo(o1));
    for(int i=0;i<k;i++){
        q.offer(arr[i]);
    }
    for(int i=k;i<arr.length;i++){
        if(q.peek()>arr[i]){
            q.offer(arr[i]);
        }
    }   
    while(q.isEmpty()){
        res.add(q.poll());
    }
    return res;
}

大根堆特性：任何父节点优先级高于子节点，堆顶节点优先级最高
解析：
1、将数组中前K个元素插入堆中，构建一个含有K个节点的大根堆，堆顶元素是最大值
2、将剩余元素依次插入堆中，每一次将插入元素和堆顶元素进行比较，若小于堆顶元素则插入
3、最终堆中保留的元素绝对是数组中最小的前K个值

· 2