leetCode刷题记录-单调队列

发表于 分类于 ，

239. 滑动窗口最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例 1：

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]
解释：
滑动窗口的位置                最大值

---------------               -----

[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

参考官方题解，或者是labuladong

自己的解法,用数组模拟，shift空间复杂度太高了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
var maxSlidingWindow = function(nums, k) {
  const sw = new SliderWindow()
  const rs = []
  for(let i=0;i<k;i++){
    sw.push(i, nums[i])
  }
  rs.push(sw.max())
  for(let i=k,j=0;i<nums.length;i++,j++){
    sw.push(i, nums[i])
    sw.shift(j, nums[j])
    rs.push(sw.max())
  }
  return rs
};
class SliderWindow{
  constructor(){
    this.arr = []
  }
  max(){
    return this.arr[0].value
  }
  shift(index, value){
    if(index === this.arr[0].index){
      this.arr.shift()
    }
  }
  push(index, value){
    while(this.arr.length!==0 && value > this.arr[this.arr.length-1].value){
      this.arr.pop()
    }
    this.arr.push({
      index,
      value
    })
  }
}

改为用双向链表模拟单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class ListNode{
  constructor(index, value, pre, next) {
    this.index = index;
    this.value = value;
    this.pre = pre || null;
    this.next = next || null;
  }
}
var maxSlidingWindow = function(nums, k) {
  const sw = new SliderWindow()
  const rs = []
  for(let i=0;i<k;i++){
    sw.push(i, nums[i])
  }
  rs.push(sw.max())
  for(let i=k,j=0;i<nums.length;i++,j++){
    sw.push(i, nums[i])
    sw.shift(j)
    rs.push(sw.max())
  }
  return rs
};
class SliderWindow{
  constructor(){
    this.dummyHead = new ListNode(-1, -1)
    this.dummyTail = new ListNode(-1, -1)
    this.dummyTail.pre = this.dummyHead
    this.dummyHead.next = this.dummyTail
  }
  max(){
    return this.dummyHead.next.value
  }
  shift(index){
    if(index === this.dummyHead.next.index){
      this.dummyHead.next = this.dummyHead.next.next
      this.dummyHead.next.pre = this.dummyHead
    }
  }
  push(index, value){
    while(this.dummyHead.next !== this.dummyTail  && value > this.dummyTail.pre.value){
      this.dummyTail.pre.pre.next = this.dummyTail
      this.dummyTail.pre = this.dummyTail.pre.pre
    }
    const newListNode = new ListNode(index, value)
    this.dummyTail.pre.next = newListNode
    newListNode.pre = this.dummyTail.pre
    this.dummyTail.pre = newListNode
    newListNode.next = this.dummyTail
  }
}

改成链表以后，速度快了非常多，思路还是一样的，就是单调队列用双向链表来实现

image-20211109113118826

76. 最小覆盖子串

自己的代码，根据labuladong这个思路书写的代码，倒数第二个测试用例超时了，原因应该是符合条件的函数需要优化吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
var minWindow = function(s, t) {
  let min = Number.MAX_SAFE_INTEGER;
  let left = right = 0;
  let res = ""
  const need = t.split("").reduce((pre, cur) => {
    pre[cur] ? pre[cur]++ : pre[cur]=1
    return pre
  }, {})
  const sw = new SliderWindow()
  while (right < s.length) {
    let flag = false
    sw.push(s[right++])
    
    while (sw.isAccord(need)) {
      sw.shift(s[left++])
      flag = true
    }
    if (flag && right - left + 1 < min) {
      min = right - left + 1
      res = s.substring(left-1, right)
    }
  }
  return res
};
class SliderWindow{
  constructor(){
    this.window = {}
  }
  push(s){
    this.window[s] ? this.window[s]++ : this.window[s] = 1
  }
  shift(s){
    this.window[s] === 1 ? delete this.window[s] : this.window[s]--
  }
  isAccord(need){
    for(let [key, value] of Object.entries(need)){
      if(!this.window[key] || this.window[key] < need[key]){
        return false
      }
    }
    return true
  }
}

优化了匹配符合条件的方式,有很多细节，标注在代码里了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
var minWindow = function (s, t) {
  // 以防出现整个字符串就是答案的情况，其实也可以只把res=s写上
  let min = s.length+1;
  let left = right = 0;
  let res = ""
  let count = 0
  const need = t.split("").reduce((pre, cur) => {
    if (pre[cur]) {
      pre[cur]++
    } else {
      pre[cur] = 1
      count++
    }
    return pre
  }, {})
  const sw = new SliderWindow(need, count)
  while (right < s.length) {
    let flag = false
    sw.push(s[right++])
    
    while (sw.isAccord()) {
      sw.shift(s[left++])
      flag = true
    }
    if (flag && right - left + 1 < min) {
      min = right - left + 1
      res = s.substring(left-1, right)
    }
  }
  console.log(res);
  return res
};
class SliderWindow{
  constructor(need, count) {
    this.window = {}
    this.need = need
    this.needNum = count
    this.curNum = 0
  }
  push(s){
    this.window[s] ? this.window[s]++ : this.window[s] = 1
    // 用===可以在超出条件后不计算
    if (this.need[s] && this.need[s] === this.window[s]) {
      this.curNum++
    }
  }
  shift(s){
    this.window[s]--
    // 同上
    if (this.need[s] && (this.need[s] - 1 === this.window[s])) {
      this.curNum--
    }
  }
  isAccord(){
    return this.curNum === this.needNum
  }
}

567. 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

1
2
3
4
5
6
7
8
9
10
11
12
13
示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
示例 2：

输入：s1= "ab" s2 = "eidboaoo"
输出：false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/permutation-in-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个题目其实和上边的题目差不多，找到符合76题条件(只要包含就够)的字符串，只要该字符串的长度与s1一致，即是符合条件

438. 找到字符串中所有字母异位词

这个题目和567一样，只不过需要返回所有符合条件的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
var findAnagrams = function (s, t) {
  // 以防出现整个字符串就是答案的情况，其实也可以只把res=s写上
  let left = right = 0;
  let res = []
  let count = 0
  const need = t.split("").reduce((pre, cur) => {
    if (pre[cur]) {
      pre[cur]++
    } else {
      pre[cur] = 1
      count++
    }
    return pre
  }, {})
  const sw = new SliderWindow(need, count)
  while (right < s.length) {
    let flag = false
    sw.push(s[right++])
    
    while (sw.isAccord()) {
      sw.shift(s[left++])
      flag = true
    }
    if (flag && right - left + 1 === t.length) {
      res.push(left-1)
    }
  }
  return res
};
class SliderWindow{
  constructor(need, count) {
    this.window = {}
    this.need = need
    this.needNum = count
    this.curNum = 0
  }
  push(s){
    this.window[s] ? this.window[s]++ : this.window[s] = 1
    // 用===可以在超出条件后不计算
    if (this.need[s] && this.need[s] === this.window[s]) {
      this.curNum++
    }
  }
  shift(s){
    this.window[s]--
    // 同上
    if (this.need[s] && (this.need[s] - 1 === this.window[s])) {
      this.curNum--
    }
  }
  isAccord(){
    return this.curNum === this.needNum
  }
}

3. 无重复字符的最长子串 labuladong 题解

难度中等6383收藏分享切换为英文接收动态反馈

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

1
2
输入: s = ""
输出: 0

这道题和上边的题，思路是相差最大的，它需要找到第一次不符合条件的，从而寻找最大值

我的代码，时间复杂度和空间复杂度都不低

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
var lengthOfLongestSubstring = function(s) {
  // 处理 s=” “ 返回 1
  if(s&&!s.trim()){
    return 1
  }
  let max = 0;
  let left = right = 0;
  const sw = new SliderWindow()
  while (right < s.length) {
    let flag = true
    sw.push(s[right++])
    
    while (!sw.isAccord()) {
      if (flag) {
        flag = false
        if (right - 1 - left > max) {
          max = right - 1 - left
        }
      }
      sw.shift(s[left++])
      flag = true
    }
    // 处理不会出现不符合情况的字符串 即 s=”a“ s="abc"
    if (right - left > max) {
      max = right - left
    }
  }
  return max
};
class SliderWindow{
  constructor() {
    this.window = {}
    this.count = 0
  }
  push(s){
    this.window[s] ? this.window[s]++ : this.window[s] = 1
    if (this.window[s] === 2) {
      this.count++
    }
  }
  shift(s){
    this.window[s]--
    // 同上
    if (this.window[s] === 1) {
      this.count--
    }
  }
  isAccord(){
    return !this.count
  }
}

总结

代码主体部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let left = right = 0
while (right < s.length) {
		// 队尾加数据
    sw.push(s[right])
    right++
    
    while (sw need shink) {
    	// 对头删除数据
      sw.shift(s[left])
      left++
  		// 依据题目在合适的位置进行更新
    }
    // 依据题目在合适的位置进行更新
  }

滑动窗口类

依据条件变更isAccord条件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class SliderWindow{
  constructor(need, count) {
    this.window = {}
    this.need = need
    this.needNum = count
    this.curNum = 0
  }
  push(s){
    this.window[s] ? this.window[s]++ : this.window[s] = 1
    // 用===可以在超出条件后不计算
    if (this.need[s] && this.need[s] === this.window[s]) {
      this.curNum++
    }
  }
  shift(s){
    this.window[s]--
    // 同上
    if (this.need[s] && (this.need[s] - 1 === this.window[s])) {
      this.curNum--
    }
  }
  isAccord(){
    return this.curNum === this.needNum
  }
}