商品关键词举例_广州番禺最新头条消息_冯站长之家官网_百度投流运营

滑动窗口最大值

我们可以使用 单调队列（双端队列 Deque） 来高效地解决滑动窗口最大值问题。具体思路如下：

1. 维护一个双端队列 deque:

   • deque 中存储数组 nums 的索引，而不是值。
   • deque 中的索引对应的数值 单调递减，即 nums[deque.front()] 始终是当前窗口的最大值。

2. 遍历数组 nums，维护窗口:

   • 保证窗口大小：
     • 如果 deque.front() 对应的元素 不在窗口内（即 deque.front() < i - k + 1），则弹出 deque.front()。
   • 保持队列单调递减：
     • 从 deque 末尾删除所有 小于等于 nums[i] 的元素，以保证 deque 的单调性。
   • 将当前索引 i 加入 deque。

3. 收集结果:

   • 当 i >= k - 1 时，窗口已形成，我们将 nums[deque.front()] 作为窗口最大值存入结果。

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(nums == null || nums.length == 0){return new int[0];}int n = nums.length;int[] res = new int[n-k+1]; //结果数组Deque<Integer> deque = new LinkedList<>(); //双端队列for(int i=0;i<n;i++){//移除窗口外的元素（队列头部）if(!deque.isEmpty() && deque.peekFirst() < i-k+1){deque.pollFirst();}//维护队列单调递减(移除队列尾部小于当前值的元素)while(!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]){deque.pollLast();}//添加当前元素索引deque.offerLast(i);//记录最大值（窗口形成后，每次取队列头部元素对应的值）if(i >= k-1){res[i-k+1] = nums[deque.peekFirst()];}}return res;}
}

最小覆盖子串

解题步骤

1. 用哈希表统计 t 中字符的频率：

   • 记录 t 需要的所有字符及其个数。

2. 使用滑动窗口 (left, right 指针)：

   • right 指针不断右移，扩展窗口，直到窗口包含 t 所有字符。
   • left 指针右移，尝试缩小窗口，并更新最小子串的长度。

3. 使用 need 和 window 两个哈希表：

   • need 记录 t 需要的字符及数量。
   • window 记录当前窗口内的字符及数量。
   • valid 记录窗口内满足 need 要求的字符数。

4. 寻找最小覆盖子串：

   • 每次 valid == need.size() 时，更新最小子串。
   • left 右移缩小窗口，保证最小覆盖。

class Solution {public String minWindow(String s, String t) {if (s.length() < t.length()) return ""; // 如果 s 比 t 短，直接返回空字符串HashMap<Character, Integer> need = new HashMap<>(); // 记录 t 中字符的需求HashMap<Character, Integer> window = new HashMap<>(); // 记录当前窗口中字符的频率// 统计 t 中每个字符的出现次数for (char c : t.toCharArray()) {need.put(c, need.getOrDefault(c, 0) + 1);}int left = 0, right = 0; // 定义左右指针int valid = 0; // 记录窗口中满足 need 条件的字符个数int minLen = Integer.MAX_VALUE; // 记录最小子串的长度int start = 0; // 记录最小子串的起始位置while (right < s.length()) {// 移动右指针，扩展窗口char c = s.charAt(right);right++;// 如果 c 是 t 中需要的字符，则更新 window 计数if (need.containsKey(c)) {window.put(c, window.getOrDefault(c, 0) + 1);// 只有当 window 中该字符数量与 need 相等时，valid 才加 1if (window.get(c).equals(need.get(c))) {valid++;}}// 当窗口包含 t 的所有字符时，开始收缩左边界while (valid == need.size()) {// 更新最小子串的长度和起始位置if (right - left < minLen) {minLen = right - left;start = left;}// 移动左指针，缩小窗口char d = s.charAt(left);left++;// 如果 d 是 t 中需要的字符，更新 window 计数if (need.containsKey(d)) {if (window.get(d).equals(need.get(d))) {valid--; // 如果该字符的数量减少，valid 也要减少}window.put(d, window.get(d) - 1);}}}// 如果 minLen 没有被更新，说明没有符合条件的子串，返回空字符串return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);}
}

最大子数组和

该问题是 最大子数组和问题（Kadane's Algorithm），可以用 动态规划（DP） 以 O(n) 时间复杂度高效求解。

思路

1. 定义状态

   • 设 dp[i] 表示以 nums[i] 结尾的最大子数组和。
   • dp[i] 可能有两种情况：
     • 加入前面的子数组，即 dp[i-1] + nums[i]
     • 重新开始一个子数组，即 nums[i]
   • 状态转移方程： dp[i]=max⁡(dp[i−1]+nums[i],nums[i])dp[i] = \max(dp[i-1] + nums[i], nums[i])dp[i]=max(dp[i−1]+nums[i],nums[i])
   • 目标是求 dp[i] 中的最大值。

2. 优化空间

   • dp[i] 只和 dp[i-1] 相关，可以用一个变量 currMax 代替 dp[i]，减少空间复杂度到 O(1)。

class Solution {public int maxSubArray(int[] nums) {int currMax = nums[0]; //当前最大子数组和int globalMax = nums[0]; //记录全局最大子数组和for(int i=1;i<nums.length;i++){//计算包含nums[i]的最大子数组和currMax = Math.max(nums[i],currMax+nums[i]);//更新全局最大值globalMax = Math.max(globalMax,currMax);}return globalMax;}
}

合并区间

该问题可以使用 排序 + 线性合并 的方法来高效解决。

步骤

1. 按区间的起始位置 start 进行排序：

   • 确保合并时能按顺序遍历区间。

2. 逐个遍历区间并合并：

   • 维护一个 merged 列表用于存放合并后的区间。
   • 对于当前区间：
     • 如果与 merged 最后一个区间重叠（即 start ≤ merged 最后一个区间的 end），则合并。
     • 否则，直接加入 merged。

class Solution {public int[][] merge(int[][] intervals) {if(intervals.length == 0){return new int[0][0];}//按区间起始位置排序Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));LinkedList<int[]> merged = new LinkedList<>();for(int[] interval:intervals){//如果merged为空，或当前区间与merged最后一个区间不重叠，则直接加入if(merged.isEmpty() || merged.getLast()[1] < interval[0]){merged.add(interval);}else{//发生重叠，合并区间merged.getLast()[1] = Math.max(merged.getLast()[1],interval[1]);}}return merged.toArray(new int[merged.size()][]);}
}

轮转数组

核心想法：使用三次翻转来完成数组的轮转。

1. 整体翻转：

   • 先把整个数组翻转，这样后 k 个元素就跑到了前面，但顺序是反的。
   • 原数组: [1, 2, 3, 4, 5, 6, 7]   翻转后: [7, 6, 5, 4, 3, 2, 1]

2. 翻转前 k 个元素：

   • 让前 k 个元素恢复正确顺序。
   • 当前数组:   [7, 6, 5, 4, 3, 2, 1]
     翻转后:     [5, 6, 7, 4, 3, 2, 1]
      

3. 翻转剩余 n-k 个元素：

   • 让后面的元素恢复正确顺序。
   • 当前数组:   [5, 6, 7, 4, 3, 2, 1]
     翻转后:     [5, 6, 7, 1, 2, 3, 4]

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;k = k % n; //防止k超过数组长度//翻转整个数组reverse(nums,0,n-1);//翻转前k个元素reverse(nums,0,k-1);//翻转剩余部分reverse(nums,k,n-1);}//反转数组的一部分private void reverse(int[] nums,int left,int right){while(left < right){int temp = nums[left];nums[left] = nums[right];nums[right] = temp;left++;right--;}}
}