4位阿里P7被裁，合伙创业卖包子，结果每月亏损5万。。。

猿大侠 · 公众号 · 算法大数据 · 2024-10-12 12:08

正文

最近在网上看到一个帖子，4位阿里P7，35岁被裁后在杭州开了一家很有特点的包子铺，从位置，装修，产品到营销策划都精心设计，用互联网思维降维竞争普通包子铺，结果每月稳赔5万！

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

来看下今天的算法题，这题是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 < len; i++) {
        // 如果队列中队头元素和当前元素位置相差i-k，相当于队头元素要
        // 出窗口了，就把队头元素给移除。
        if (!deque.isEmpty() && deque.peekFirst() <= i - k)
            deque.pollFirst();
        // 在添加一个值之前，前面比他小的都要被移除掉，并且还要保证窗口
        // 中队列头部元素永远是队列中最大的。
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
            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 < len; i++) {
            // 如果队列中队头元素和当前元素位置相差i-k，相当于队头元素要
            // 出窗口了，就把队头元素给移除。
            if (!d.empty() && d.front() <= i - k)
                d.pop_front();
            // 在添加一个值之前，前面比他小的都要被移除掉，并且还要保证窗口
            // 中队列头部元素永远是队列中最大的。
            while (!d.empty() && nums[d.back()] < nums[i])
                d.pop_back();
            d.push_back(i);// 当前元素的下标加入到队列的尾部。
            // 当窗口的长度大于等于k个的时候才开始计算（注意这里的i是从0开始的）。
            if (i >= k - 1)
                // 队头元素是队列中最大的，把队列头部的元素加入到数组中。
                ans[index++] = nums[d.front()];
        }
        return ans;
    }

Python：

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    index, length = 0, len(nums)
    ans = [0] * (length - k + 1)
    # 双端队列，存储元素的下标
    q = deque()
    for i in range(length):
        # 如果队列中队头元素和当前元素位置相差i-k，相当于队头元素要
        # 出窗口了，就把队头元素给移除。
        if q and q[0] <= i - k:
            q.popleft()
        # 在添加一个值之前，前面比他小的都要被移除掉，并且还要保证窗口
        # 中队列头部元素永远是队列中最大的。
        while q and nums[q[-1]] < nums[i]:
            q.pop()
        q.append(i)  # 当前元素的下标加入到队列的尾部。
        # 当窗口的长度大于等于k个的时候才开始计算（注意这里的i是从0开始的）。
        if i >= k - 1:
            # 队头元素是队列中最大的，把队列头部的元素加入到数组中。
            ans[index] = nums[q[0]]
            index += 1
    return ans

来自：数据结构与算法