Dvorak
Dvorak

Dvorak Chen

Algorithms

14
JAN

滑动窗口最大值

这篇文章介绍了一种高效求解滑动窗口最大值问题的方法。作者首先提到暴力枚举的时间复杂度较高，然后转向更优方法，提出利用双端队列存储可能的最大值索引，并确保队列中元素为当前窗口内的降序排列。具体思路是：在将新元素加入队列前，移除所有比其小的元素；当窗口滑动时，检查队列头部元素是否仍在窗口内，如不在则移出。这样可保证队列首部始终为当前窗口最大值。文中通过举例和代码示例详细说明了这一过程，并解释了如何维护队列结构以确保时间复杂度为 O(n)。--DeepSeek

Algorithms Sliding Window Queue Data Structure Algorithm Optimization Time Complexity Analysis Max Value Problem
26
MAY

KMP 算法

文章介绍了KMP（Knuth-Morris-Pratt）算法在字符串匹配中的应用。首先通过构建`next`数组来记录模式字符串的最长前缀后缀匹配长度，避免重复比较字符以提高效率；然后利用该数组在目标字符串中查找子串。`getNext`函数采用双指针技术构建`next`数组，时间复杂度为O(n)，其中n为模式字符串的长度。主函数`strStr`通过遍历目标字符串并结合`next`数组调整匹配位置，最终实现高效查找，避免暴力搜索的时间浪费。--DeepSeek

Algorithms KMP KMP Algorithm String Matching Next Array Efficient Search
  • 1