代码随想录算法训练营第十一天| 150. 逆波兰表达式求值、239. 滑动窗口最大值、347.前 K 个高频元素

150. 逆波兰表达式求值

思路：遇到数字入栈，遇到字符，出栈中的两个数字，然后计算，得到的结果再入栈。

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack();

        for(String s : tokens){
            if ("+".equals(s)) {    
                stack.push(stack.pop() + stack.pop());      
            } else if ("-".equals(s)) {
                stack.push(-stack.pop() + stack.pop());
            } else if ("*".equals(s)) {
                stack.push(stack.pop() * stack.pop());
            } else if ("/".equals(s)) {
                int temp1 = stack.pop();
                int temp2 = stack.pop();
                stack.push(temp2 / temp1);
            } else {
                stack.push(Integer.valueOf(s));
            }
        }
        return stack.pop();
        
    }
}

 239. 滑动窗口最大值（难）

代码录思路：自己diy一个数据结构，其类似于双端队列。扫描前k个元素，入队时，先与队尾元素比较，若队尾元素比要添加的元素小，则将队尾元素排出（这可以保证队头位置的元素一直为最大元素）。当窗口后移时，要将窗口前边元素移出，则需要判断窗口移除元素是否为队头元素，若是，则移除队头元素，若不是，则代表已经移除。将窗口后边元素移入时调用入队操作即可。

class Myqueue{
    Deque<Integer> deque;
    public Myqueue(){
        deque = new LinkedList<>();
    }
    void add(int num){
        while(!deque.isEmpty() && num > deque.getLast()){
            deque.pollLast();
        }
        deque.add(num);
    }
    void delete(int num){
        if(!deque.isEmpty() && deque.getFirst() == num){
            deque.pollFirst();
        }
    }
    int getMax(){
        return deque.peek();
    }
}

class Solution {

    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] res = new int[nums.length-k+1];

        Myqueue myqueue = new Myqueue();
        
        for(int i = 0;i < k;i++){
            myqueue.add(nums[i]);
        }

        res[0] = myqueue.getMax();

        for(int i = k; i < nums.length;i++){
            //先移除窗口头部元素；
            myqueue.delete(nums[i-k]);
            //加入下一个元素;
            myqueue.add(nums[i]);
            //获取最大值
            res[i-k+1] = myqueue.getMax();
        }

        return res;

        
    }
}

 347.前 K 个高频元素（难）

代码录思路：先用map记录元素及其出现的次数，然后用优先级队列（小顶堆），记录前k个高频元素。

代码中好多方法都不熟练

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<Integer, Integer>();
        //遍历数组，得到每个元素出现的次数
        for (int num : nums) {
			map.put(num, map.getOrDefault(num, 0) + 1);
		}
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((value1,value2)->value1[1]-value2[1]);
        //获取出现次数最多的k个元素，放到pq中
        for(Map.Entry<Integer, Integer> value : map.entrySet() ) {
        	if(pq.size() < k) {//元素少于k个时，直接加入
        		pq.add(new int[] {value.getKey(),value.getValue()});
        	}else {//元素大于k个时分情况
        		if(value.getValue() > pq.peek()[1]) {//元素出现次数比队列中出现次数最少的多时，加入
        			pq.poll();
        			pq.add(new int[] {value.getKey(),value.getValue()});
        		}
        	}
        }
        
        int[] res = new int[k];
        for(int i = k-1;i>=0;i--) {
        	res[i] = pq.poll()[0];
        }
        return res;
        
    }
}

鉴于作者水平有限，文章可能存在错误

如有指正，十分感谢