重庆推广网站,建设工程施工合同模板,品牌网站怎么建立,wordpress如何还原解题思路#xff1a;
初始化窗口元素#xff1a; 遍历前 k 个元素#xff0c;构建初始单调队列。若当前索引对应值大于等于队尾索引对应值#xff0c;移除队尾索引#xff0c;将当前索引加入队尾。遍历结束时当前队头索引即为当前窗口最大值#xff0c;将其存入结果数组…
解题思路
初始化窗口元素 遍历前 k 个元素构建初始单调队列。若当前索引对应值大于等于队尾索引对应值移除队尾索引将当前索引加入队尾。遍历结束时当前队头索引即为当前窗口最大值将其存入结果数组。处理剩余元素 对于 k1 之后的元素加入规则同上。若队头索引已不在当前窗口范围内即deque.peekFirst() i - k则移除队头索引。当前队头索引即为窗口最大值将其存入结果数组。
Java代码
public class Solution {public int[] maxSlidingWindow(int[] nums, int k) {int n nums.length;DequeInteger deque new ArrayDeque();for (int i 0; i k; i) {while (!deque.isEmpty() nums[i] nums[deque.peekLast()]) {deque.pollLast();}deque.offerLast(i);} int[] res new int[n - k 1];res[0] nums[deque.peekFirst()];for (int i k; i n; i) {while (!deque.isEmpty() nums[i] nums[deque.peekLast()]) {deque.pollLast();}deque.offerLast(i);if (deque.peekFirst() i - k) {deque.pollFirst();}res[i - k 1] nums[deque.peekFirst()];}return res;}
}复杂度分析 时间复杂度 O(n)每个元素最多入队和出队一次因此总操作次数为线性时间。 空间复杂度 O(k)最坏情况下队列中存储窗口内所有元素的索引当数组严格递减时。 解题思路
字符统计初始化 使用两个长度为 256 的数组 countT 和 countS分别统计 t 中每个字符的出现次数以及当前窗口中 s 的字符出现次数。滑动窗口遍历 右指针 r遍历 s将字符纳入窗口并更新 countS。左指针 l当窗口满足包含 t 所有字符的条件时尽可能向右收缩窗口以寻找更小的有效窗口。窗口有效性判断 通过 isInclude 方法检查当前窗口的字符是否覆盖了 t 的所有字符。更新最小窗口 每次找到有效窗口时记录其长度和位置最终返回最小的窗口子串。
Java代码
class Solution {public String minWindow(String s, String t) {char[] S s.toCharArray();char[] T t.toCharArray();int n S.length;int left -1;int right n;int[] countS new int[128];int[] countT new int[128];for (int i 0; i T.length; i) {countT[T[i]];}int l 0;for (int r 0; r n; r) {countS[S[r]];while (isInclude(countS, countT)) {if (r - l right - left) {right r;left l;}countS[S[l]]--;l;}}return left 0 ? : s.substring(left, right 1);}public boolean isInclude(int[] countS, int[] countT) {for (int i 0; i 128; i) {if (countS[i] countT[i]) {return false;}}return true;}
}复杂度分析
时间复杂度 O(n)左右指针移动最多 2n 次。空间复杂度 O(1)使用固定大小的数组与输入规模无关。
