算法训练（leetcode）二刷第十天 | 150. 逆波兰表达式求值、*239. 滑动窗口最大值、*347. 前 K 个高频元素

150. 逆波兰表达式求值

leetcode题目地址

对后缀表达式求值。题目给的是一个合法后缀表达式，因此无需额外判断其合法性。

借助一个栈来存储数字，当遇到符号时弹出两个数字，先弹出的是符号右边的数字，后弹出的是符号坐边的数字，然后按照对应符号操作过后再放回栈中。

时间复杂度： $O(n)$
空间复杂度： $O(n)$

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

        for(int i=0; i<tokens.length; i++){
            String chs = tokens[i];
            if(chs.equals("+") || chs.equals("-") || 
            chs.equals("*") || chs.equals("/")){
                int a = numbers.pop();
                int b = numbers.pop();
                if(chs.equals("+")){
                    numbers.push(a+b);
                }else if(chs.equals("-")){
                    numbers.push(b-a);
                }else if(chs.equals("*")){
                    numbers.push(b*a);
                }else{
                    numbers.push(b/a);
                }
            }else{
                numbers.push(Integer.parseInt(chs));
            }
        }
        return numbers.pop();

    }
}

*239. 滑动窗口最大值

leetcode题目地址

思路一

窗口每次向后滑动一个位置，因此只需要比较新进入窗口的元素与上一个窗口中的最大值（若仍在当前窗口中）。若上一窗口中的最大值不在当前窗口，则需要重新寻找最大值。

时间复杂度： $O(n\ast k)$
空间复杂度： $O(1)$

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

        int maxIdx = -1;
        for(int i=0; i<len; i++){
            int left = i;
            int right = left+k-1;
            // 越界
            if(right>=len) break;
            // 上一组最大值仍在当前窗口内
            if(maxIdx>=left && maxIdx<right){
                // 新纳入的元素大于等于最大元素，更新索引
                if(nums[maxIdx] <= nums[right]) maxIdx = right;
            }else{
                // 上一组最大值不在当前窗口内，重新在当前窗口中找出最大值
                maxIdx = left;
                for(int j=left; j<=right; j++){
                    if(nums[j] >= nums[maxIdx]) maxIdx = j;
                }
            }
            res[i] = nums[maxIdx];
        }
        return res;
    }
}

思路二：单调队列

将每一个窗口看作一个队列，每移动一次可以看作求当前队列内的最大元素。
维护一个单调队列。使用双端队列，从前到后单调不增。

• 入队时判断队列尾部元素是否大于当前元素，若小于当前元素则弹出，直至不小于。
• 队列头部到尾部始终是单调不增的。

窗口每移动一次，即对窗口左侧元素进行出队，窗口右侧元素进行入队。

时间复杂度： $O(n)$
空间复杂度： $O(k)$

// java
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int len = nums.length;
        int[] res = new int[len-k+1];
        // 双端队列存储单调队列的下标
        ArrayDeque<Integer> deque = new ArrayDeque<>();
        int idx = 0;
        for(int i=0; i<len; i++){
            // 弹出队头窗口外的元素
            while(!deque.isEmpty() && deque.peek() < i-k+1){
                deque.poll();
            }

            // 弹出队尾小于当前元素的元素
            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]){
                deque.pollLast();
            }
            // 入队当前元素
            deque.offer(i);

            if(i>=k-1) {
            	// 记录当前窗口最大值
                res[idx++] = nums[deque.peek()];
            }
        }
        return res;
    }
}

*347. 前 K 个高频元素

leetcode题目地址

题解思路

时间复杂度： $O(n)$
空间复杂度： $O(n)$

// java