米哈游（原神）在上海真是神奇的存在，985硕5连简历都过不了。。。

猿大侠 · 公众号 · · 2024-04-10 12:08

正文

一网友因为简历在米哈游没有通过，发文称：米哈游在上海真是神奇的存在，985硕5，米哈游简历都过不了，真的c9才行吗？

首先来说米哈游不可能都是c9 的（九校联盟：北京大学、清华大学、哈尔滨工业大学、复旦大学、上海交通大学、南京大学、浙江大学、中国科学技术大学、西安交通大学），简历过不了只能说不匹配，也有可能是运气问题，比如正好投递的那段时间该岗位不招人，只好拒了。

有的网友好奇不招人为什么招聘职位还挂着，这是因为很多公司在招聘软件上买的有会员，即便招到人了也不愿意下架，一方面如果过段时间又有员工离职还可以继续招，另一方面一直挂着还可以给公司打广告（反正已经买了会员），所以我们经常会看到有些公司常年招聘，如果你投的话有时候他们连看都不会看。

--------------下面是今天的算法题--------------

来看下今天的算法题，这题是LeetCode的第239题：滑动窗口最大值。这题在字节，永辉超市和中国移动都考过，我们来看下。

问题描述

来源：LeetCode第239题

难度：困难

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

示例1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3

输出：[3,3,5,5,6,7]

解释：

滑动窗口的位置最大值

--------------- -----

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

示例2：

输入：nums = [1], k = 1

输出：[1]

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

问题分析

这题让计算滑动窗口中的最大值，窗口我们可以把它看作是一个单调队列，只需要维护这个队列即可。在添加元素之前如果前面有比他小的都要被移除，保证队列的单调性，即从左往右是递减的，所以队列中的最大值就是最左边的元素。

为什么可以这样解，因为队列中左边的元素肯定是比右边的元素先出队列的，如果添加的元素比它左边的元素大，它左边的那个元素不可能是队列中的最大值，所以可以把它给移除。我们以示例 1 为例画个图来看下。

JAVA：

public int[] maxSlidingWindow(int[] nums, int k) {
    int index = 0, len = nums.length;
    int[] ans = new int[len - k + 1];
    // 双端队列，存储元素的下标
    Deque deque = new ArrayDeque<>();
    for (int i = 0; i         // 如果队列中队头元素和当前元素位置相差i-k，相当于队头元素要
        // 出窗口了，就把队头元素给移除。
        if (!deque.isEmpty() && deque.peekFirst() <= i - k)
            deque.pollFirst();
        // 在添加一个值之前，前面比他小的都要被移除掉，并且还要保证窗口
        // 中队列头部元素永远是队列中最大的。
        while (!deque.isEmpty() && nums[deque.peekLast()]             deque.pollLast();
        deque.addLast(i);// 当前元素的下标加入到队列的尾部。
        // 当窗口的长度大于等于k个的时候才开始计算（注意这里的i是从0开始的）。
        if (i >= k - 1)
            // 队头元素是队列中最大的，把队列头部的元素加入到数组中。
            ans[index++] = nums[deque.peekFirst()];
    }
    return ans;
}

C++：

public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k) {
        int index = 0, len = nums.size();
        vector<int> ans(len - k + 1);
        // 双端队列，存储元素的下标
        deque<int> d;
        for (int i = 0; i             // 如果队列中队头元素和当前元素位置相差i-k，相当于队头元素要
            // 出窗口了，就把队头元素给移除。
            if (!d.empty() && d.front() <= i - k)
                d.pop_front();
            // 在添加一个值之前，前面比他小的都要被移除掉，并且还要保证窗口
            // 中队列头部元素永远是队列中最大的。
            while (!d.empty() && nums[d.back()]                 d.pop_back();
            d.push_back(i);// 当前元素的下标加入到队列的尾部。
            // 当窗口的长度大于等于k个的时候才开始计算（注意这里的i是从0开始的）。
            if (i >= k - 1)
                // 队头元素是队列中最大的，把队列头部的元素加入到数组中。

米哈游（原神）在上海真是神奇的存在，985硕5连简历都过不了。。。

正文

请到「今天看啥」查看全文