企业官网建设流程全解析

网站优化怎样做,吉林市市政建设集团网站,免费发布推广的网站,做网站招商需要具备什么这道题是 LC 239. 滑动窗口最大值 (Hard)。 它是所有涉及“区间最值”问题的鼻祖。面试官考这道题#xff0c;看的就是你能不能在 O(N) 的时间里解决问题#xff0c;而不是傻傻地用 O(NK) 去遍历。 场景想象#xff1a; 有一个固定长度为 k 的窗口在数组上滑动。这就好比一…这道题是LC 239. 滑动窗口最大值(Hard)。 它是所有涉及“区间最值”问题的鼻祖。面试官考这道题看的就是你能不能在 O(N) 的时间里解决问题而不是傻傻地用 O(N×K) 去遍历。场景想象有一个固定长度为k的窗口在数组上滑动。这就好比一个**“淘汰制的晋升通道”**。规则 1能力说话如果你比前面的老员工队列里的元素能力强数值大那前面的老员工就废了永远不可能成为这个窗口里的老大最大值直接把他们踢走。规则 2任期限制你是这一届最强的队头但如果你的任期到了滑出了窗口范围你也得退休。力扣 239. 滑动窗口最大值https://leetcode.cn/problems/sliding-window-maximum/题目分析输入整数数组nums窗口大小k。输出数组包含每次滑动后的最大值。例子nums [1, 3, -1, -3, 5, 3, 6, 7], k 3[1, 3, -1]- Max: 3[3, -1, -3]- Max: 3[-1, -3, 5]- Max: 5...核心思维单调队列 (Monotonic Queue)我们需要维护一个双端队列 (Deque)。 为了保证队头永远是最大值这个队列里的元素必须严格单调递减从大到小。队列里存什么存下标 (index)而不是存数值。为什么因为我们需要通过下标来判断队头元素是否已经**“过期”**滑出窗口。如果只存数值就不知道它什么时候该退休了。操作三部曲入队去尾新元素nums[i]来了。如果队尾元素 新元素说明队尾是个“又老又弱”的废棋直接pop踢掉。重复这个过程直到队尾元素 新元素或者队列空了。把nums[i]的下标放入队尾。(这一步保证了队列是单调递减的)出队去头检查队头下标是否已经小于i - k 1即是否滑出了当前窗口。如果是shift踢掉队头。记录结果只要窗口形成i k - 1队头元素对应的数值就是当前窗口的最大值。代码实现 (JavaScript)JavaScript/** * param {number[]} nums * param {number} k * return {number[]} */ var maxSlidingWindow function(nums, k) { // 队列存放的是下标 index const queue []; const result []; for (let i 0; i nums.length; i) { // 1. 【入队前的清理】维护单调递减 // 只要队尾元素比当前元素小就把它踢走 // 因为当前元素更强而且更晚离开窗口所以队尾那些“弱者”永远没机会出头了 while (queue.length 0 nums[queue[queue.length - 1]] nums[i]) { queue.pop(); } // 新元素入队 (存下标) queue.push(i); // 2. 【检查队头合法性】老大多久退休 // 计算窗口左边界i - k 1 // 如果队头下标 i - k 1说明它已经滑出去了 if (queue[0] i - k) { queue.shift(); // 移除队头 } // 3. 【记录结果】 // 只有当窗口完全形成后也就是 i 走到 k-1 时才开始记录 if (i k - 1) { // 队头永远是当前窗口的最大值 result.push(nums[queue[0]]); } } return result; };深度模拟nums [1, 3, -1, -3, 5],k 3i0 (值1): 队列[0](对应值1)。i1 (值3):3 比 1 大 - 弹出 0。入队 1。队列[1](对应值3)。i2 (值-1):-1 比 3 小 - 保持单调性。入队 2。队列[1, 2](对应值 3, -1)。窗口成型记录最大值nums[1] 3。Res[3]i3 (值-3):-3 比 -1 小 - 入队 3。队列[1, 2, 3](对应值 3, -1, -3)。检查队头队头是 1。当前窗口范围[1, 3]。队头还在不用退休。记录最大值nums[1] 3。Res[3, 3]i4 (值5):5 比 -3 大 - 弹 3。5 比 -1 大 - 弹 2。5 比 3 大 - 弹 1。入队 4。队列[4](对应值 5)。记录最大值nums[4] 5。Res[3, 3, 5]总结这道题是单调队列的入门即巅峰。 请记住这个“职场法则”一旦新来的比你强你就被淘汰了pop即使你是最强的时间到了也得走人shift。下一题预告K 个不同整数的子数组这一题LC 239解决的是“窗口内的最值”。 下一题LC 992. K 个不同整数的子数组专项十我们要解决的是一个极具数学技巧的计数问题。题目求有多少个子数组恰好包含K种不同的整数。难点直接求“恰好 K”很难。我们需要把问题转化为“最多 K” - “最多 K-1”。这是一个非常高级的滑动窗口思想。准备好迎接双指针专题的大结局了吗