剑指offer-64、滑动窗⼝的最⼤值
<h2 id="题描述">题⽬描述</h2><p>给定⼀个数组和滑动窗⼝的⼤⼩，找出所有滑动窗⼝⾥数值的最⼤值。例如，如果输⼊数组 {2,3,4,2,6,2,5,1} 及滑动窗⼝的⼤⼩ 3 ，那么⼀共存在 6 个滑动窗⼝，他们的最⼤值分别为 {4,4,6,6,6,5} ；</p>
<p>针对数组 {2,3,4,2,6,2,5,1} 的滑动窗⼝有以下6个： {,2,6,2,5,1} ， {2,,6,2,5,1} ， {2,3,,2,5,1} ， {2,3,4, ,5,1} ， {2,3,4,2,,1} ， {2,3,4,2,6,} 。 窗⼝⼤于数组⻓度的时候，返回空。</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="暴力法">暴力法</h3>
<p>遍历每个可能的窗口起始位置，计算窗口内的最大值</p>
<pre><code class="language-java">public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
// 处理边界情况
if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
return new int;
}
int n = nums.length;
int[] result = new int; // 结果数组
// 遍历每个窗口的起始位置
for (int i = 0; i <= n - k; i++) {
int max = Integer.MIN_VALUE;
// 计算当前窗口内的最大值
for (int j = i; j < i + k; j++) {
if (nums > max) {
max = nums;
}
}
result = max;
}
return result;
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n×k)，需要处理n-k+1个窗口，每个窗口需要k次比较</li>
<li><strong>空间复杂度</strong>：O(1)，除结果数组外只使用常数空间</li>
</ul>
<h3 id="双端队列法最优解">双端队列法（最优解）</h3>
<p>⾸先进⾏⾮空判断，以及数组⻓度是否不为 0 ，是否不⼩于窗⼝⻓度。</p>
<p>其次，使⽤⼀个双向链表，⾥⾯保存的是索引，遍历每⼀个元素，如果双向队列不为空且最后的元素作为索引的数值⼩于当前的元素，就把当前的元素的索引加到队列的后⾯。（这样可以保证队列从头到尾是单调递减的，也就是队尾的元素就是最⼩的元素）。</p>
<p>然后把当前的元素加进去队列尾部。判断队列前⾯的元素是不是索引位置不符合，如果不符合，就移除队列头部的元素。</p>
<p>那么此时的队列⾸部肯定就是滑动窗⼝的最⼤值。（此处应该判断滑动窗⼝⽣效的索引）</p>
<p>以 2, 3, 4, 2, 6, 2, 5, 1 为例：</p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504212346665.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504212346511.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504212346071.png" alt="" loading="lazy"></p>
<p><img src="https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202504212346700.png" alt="" loading="lazy"></p>
<p>所有的窗⼝最⼤值⾄此已经收集完成。</p>
<pre><code class="language-java">public class Solution64 {
public static void main(String[] args) {
int[] nums = {2, 3, 4, 2, 6, 2, 5, 1};
System.out.println(new Solution64().maxInWindows(nums, 3));
}
public ArrayList<Integer> maxInWindows(int[] num, int size) {
ArrayList<Integer> results = new ArrayList<>();
if (num == null || num.length == 0 || num.length < size || size <= 0) {
return results;
}
LinkedList<Integer> integers = new LinkedList<>();
for (int i = 0; i < num.length; i++) {
while (!integers.isEmpty() && num < num) {
integers.removeLast();
}
integers.addLast(i);
while (i - integers.peekFirst() >= size) {
integers.removeFirst();
}
if (i >= size - 1) {
results.add(num);
}
}
return results;
}
}
</code></pre>
<ul>
<li>时间复杂度：O（n）,所有的元素都进⼊队列，再出队列</li>
<li>空间复杂度：O(n)，使⽤额外的队列空间存储索引以及窗⼝最⼤值。</li>
</ul>
<h3 id="动态规划法分块思想">动态规划法（分块思想）</h3>
<p>将数组分成大小为k的块，预处理每个位置的左右最大值</p>
<p><strong>分块思想：</strong></p>
<ul>
<li>将数组划分为大小为k的块（最后一块可能不满）</li>
<li><code>left</code>：从当前块开始到位置i的最大值</li>
<li><code>right</code>：从位置i到当前块结束的最大值</li>
</ul>
<p><strong>窗口最大值计算：</strong></p>
<p>对于窗口：</p>
<ul>
<li>如果窗口完全在一个块内：<code>right</code>或<code>left</code>就是最大值</li>
<li>如果窗口跨越两个块：最大值 = max(右块的左最大值, 左块的右最大值)</li>
</ul>
<pre><code class="language-java">public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
return new int;
}
int n = nums.length;
if (k == 1) return nums; // 窗口大小为1，直接返回原数组
int[] left = new int;// 从左到右的块最大值
int[] right = new int; // 从右到左的块最大值
int[] result = new int;
// 构建left数组：从左到右的块内最大值
left = nums;
for (int i = 1; i < n; i++) {
if (i % k == 0) {
// 块的首元素，重新开始计算
left = nums;
} else {
// 与前一个位置比较取最大值
left = Math.max(left, nums);
}
}
// 构建right数组：从右到左的块内最大值
right = nums;
for (int i = n - 2; i >= 0; i--) {
if ((i + 1) % k == 0) {
// 块的尾元素，重新开始计算
right = nums;
} else {
// 与后一个位置比较取最大值
right = Math.max(right, nums);
}
}
// 计算每个窗口的最大值
for (int i = 0; i <= n - k; i++) {
// 窗口最大值 = max(右端点的左最大值, 左端点的右最大值)
result = Math.max(right, left);
}
return result;
}
}
</code></pre>
<p><strong>算法分析：</strong></p>
<ul>
<li><strong>时间复杂度</strong>：O(n)，三次线性遍历</li>
<li><strong>空间复杂度</strong>：O(n)，需要两个辅助数组</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19468619
頁:
[1]