前端滑动窗口和滚动窗口运用到的知识点有哪些?具体代码体现在哪里?请详细列举出来。
时间: 2024-03-03 15:53:56 浏览: 21
前端滑动窗口和滚动窗口主要运用到的知识点包括数组、双指针、队列和动态规划等。
滑动窗口是指在一个固定长度的窗口内进行滑动,通常用双指针实现,具体代码体现在以下几个方面:
1. 初始化双指针left和right,分别指向窗口的左右边界。
2. 在while循环中,每次移动右边界,直到满足某个条件(如窗口内元素的和等于一个固定值、窗口内元素个数等于一个固定值等)。
3. 然后移动左边界,直到不再满足该条件,再次移动右边界,以此类推,直到右边界到达数组末尾。
以下是一个求解最长无重复字符子串的滑动窗口代码示例:
```javascript
function lengthOfLongestSubstring(s) {
let left = 0, right = 0, maxLen = 0;
const map = new Map();
while (right < s.length) {
const char = s[right];
if (map.has(char) && map.get(char) >= left) {
left = map.get(char) + 1;
}
map.set(char, right);
maxLen = Math.max(maxLen, right - left + 1);
right++;
}
return maxLen;
}
```
滚动窗口是指在一个可变长度的窗口内进行滚动,通常用队列实现,具体代码体现在以下几个方面:
1. 初始化队列queue,将初始元素加入队列。
2. 在while循环中,每次判断队列中的元素是否满足某个条件(如窗口内元素的和等于一个固定值、窗口内元素个数等于一个固定值等)。
3. 如果满足条件,更新结果;否则,从队列中删除一个元素,继续判断。
以下是一个求解滑动窗口最大值的滚动窗口代码示例:
```javascript
function maxSlidingWindow(nums, k) {
const queue = [];
const res = [];
for (let i = 0; i < nums.length; i++) {
if (i >= k && queue[0] <= i - k) {
queue.shift();
}
while (queue.length && nums[queue[queue.length - 1]] < nums[i]) {
queue.pop();
}
queue.push(i);
if (i >= k - 1) {
res.push(nums[queue[0]]);
}
}
return res;
}
```