LCR 078. 合并 K 个升序链表的感想

[musings]
今天写了下 https://leetcode.cn/problems/vvXgSW/description/ ,其实不是特别难,暴力写法也还行但是排序的时间复杂度用堆可以从O(N)压缩到O(log N),但是在用堆写的时候就碰到点问题,js没有内置堆,就手写一个,手写的过程中有几个小问题引发的深思,记录下

Q1:pop和peak的区别?
A: Peak就是游戏里的peak,看一眼最大值,不拿走….

Q2:为什么大顶堆(举例)在pop的时候官方写的版本需要把头尾呼唤然后pop,而不是直接用shift?
A: 如果头尾不互换,直接使用shift,则数组所有位置都会移动,直接破坏了顶堆的特性,那重新排序的时间复杂度就变成O(n),如果把头尾互换,然后删掉尾部,那么只会破坏最头部的最大值顺序,可以只针对顶部元素去做排序,时间复杂度就是O(logn).

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
class MaxStack {
    private stack: number[];
    constructor() {
        this.stack = [];
    }

    push(val: number) {
        this.stack.push(val);
        this.sortFromBottom();
    }

    sortFromBottom() {
        let currentIndex = this.getLastIndex();
        while (true) {
            let parentIndex = this.getParentIndex(currentIndex);
            if (currentIndex < 0 || parentIndex < 0 || this.stack[parentIndex] > this.stack[currentIndex]) {
                break;
            } else {
                this.swap(parentIndex, currentIndex);
                currentIndex = parentIndex;
            }
        }
    }

    pop() {
        this.swap(0, this.getLastIndex());
        const popVal = this.stack.pop();
        this.sortFromTop();
        return popVal;
    }

    sortFromTop() {
        let currentIndex = 0;
        while (true) {
            let leftIndex = this.getLeftIndex(currentIndex);
            if(leftIndex>this.getLastIndex()) break; //如果没有左节点直接退出
            let rightIndex = this.getRightIndex(currentIndex);
            let leftVal = this.stack[leftIndex];
            let rightVal = this.stack[rightIndex];
            let currentVal = this.stack[currentIndex];
            if (currentIndex == this.getLastIndex() || (currentVal > rightVal && currentVal > leftVal)) break;
            let maxInd = leftVal > rightVal ? leftIndex : rightIndex;
            if (leftIndex > this.getLastIndex() || rightIndex > this.getLastIndex() || this.stack[maxInd] <= currentVal) break;
            else {
                this.swap(maxInd, currentIndex);
                currentIndex = maxInd;
            }
        }
    }

    getLastIndex(): number {
        return this.stack.length - 1;
    }

    getParentIndex(i: number): number {
        return Math.floor((i - 1) / 2);
    }

    getLeftIndex(i: number): number {
        return 2 * i + 1;
    }
    getRightIndex(i: number): number {
        return 2 * i + 2;
    }

    swap(index1: number, index2: number) {
        let temp = this.stack[index1];
        this.stack[index1] = this.stack[index2];
        this.stack[index2] = temp;
    }
    peak(): number {
        return this.stack[0];
    }
    print() {
        return [...this.stack];
    }
}


let a = new MaxStack();
a.push(4)
a.push(14)
a.push(8)
a.push(16)
a.push(24)
a.push(9)
a.push(11)
a.push(15)
a.push(34)
a.push(26)
console.log(a.print());

a.pop();
console.log(a.print());