算法基础算法

惰性更新

字数统计: 1.1k字   |   阅读时长: 4分
, , ,

摘要: 惰性更新的经典问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

惰性更新是一种常见的思想，简单理解就是将更新操作存下来，但是不实际执行更新，而当查询的内容需要更新后的结果的时候，才执行更新，如果更新操作比较密集，而查询操作比较稀少，惰性更新可能会省下很多无效的更新操作，从而提升效率。

这种惰性更新的思想，按照保存的序列的内容，有以下几类常见的场景：

本文我们通过一个题目来理解这种惰性更新的思想在维护数据结构过程中的应用。

$1 题目

栈排序。 编写程序，对栈进行排序使最小元素位于栈顶。最多只能使用一个其他的临时栈存放数据，但不得将元素复制到别的数据结构（如数组）中。该栈支持如下操作：push、pop、peek 和 isEmpty。当栈为空时，peek 返回 -1。

说明:

1
栈中的元素数目在[0, 5000]范围内。

示例1:
输入：
[“SortedStack”, “push”, “push”, “peek”, “pop”, “peek”]
[[], [1], [2], [], [], []]
输出：
[null,null,null,1,null,2]

示例2:
输入：
[“SortedStack”, “pop”, “pop”, “push”, “pop”, “isEmpty”]
[[], [], [], [1], [], []]
输出：
[null,null,null,null,null,true]

$2 题解

算法：双栈

主栈 st，按弹出顺序保存所有已压入数据，辅助栈 st_sort，用于周转数据。

1
2
push(x): 将 st 中比 x 小的转移至 st_sort，将 x 压入 st，然后再将 st_sort 中元素转移回 st。这样的话对于所有已经进栈的元素 x，比 x 小的一定比 x 先出栈，比 x 大的一定比 x 后出栈
pop(x): 仅需将 st 的栈顶弹出

代码(c++)

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
class SortedStack {
public:
    SortedStack() {
        st_sort = stack<int>();
        st = stack<int>();
    }

    void push(int val) {
        while(!st_sort.empty() && st_sort.top() < val)
        {
            st.push(st_sort.top());
            st_sort.pop();
        }
        st_sort.push(val);
        while(!st.empty())
        {
            st_sort.push(st.top());
            st.pop();
        }
    }

    void pop() {
        if(isEmpty())
            return;
        st_sort.pop();
    }

    int peek() {
        if(isEmpty())
            return -1;
        int ans = st_sort.top();
        return ans;
    }

    bool isEmpty() {
        return st_sort.empty();
    }

private:
    stack<int> st_sort;
    stack<int> st;
};

优化：惰性更新

压入 x 时，将 st 中比 x 小的转移至 st_sort，将 x 压入 st，这里不急着将 st_sort 中的元素转移回 st。而是调用 peak() 或者 pop() 时才将 st_sort 中元素转移回 st。

按照以上思路，压入 x 时，st 和 st_sort 均有元素，其中 st 升序(栈顶元素小)，顶为 y，st_sort 降序(栈顶元素大)，顶为 z。此时要看 x 与 y, z 的关系:

  • x > y: 将 st 中小于 x 的转移到 st_sort，x 插入到 st
  • x < z: 将 st_sort 中大于 x 的元素转移回 st，x 压入到 st_sort
  • z <= x <= y: 直接将 x 压入 st

代码(c++)

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
class SortedStack {
public:
    SortedStack() {
        st_sort = stack<int>();
        st = stack<int>();
    }

    void push(int val) {
        while(!st_sort.empty() && st_sort.top() < val)
        {
            st.push(st_sort.top());
            st_sort.pop();
        }
        while(!st.empty() && st.top() > val)
        {
            st_sort.push(st.top());
            st.pop();
        }
        st_sort.push(val);
    }

    void pop() {
        if(isEmpty())
            return;
        while(!st.empty())
        {
            st_sort.push(st.top());
            st.pop();
        }
        st_sort.pop();
    }

    int peek() {
        if(isEmpty())
            return -1;
        while(!st.empty())
        {
            st_sort.push(st.top());
            st.pop();
        }
        int ans = st_sort.top();
        return ans;
    }

    bool isEmpty() {
        return st_sort.empty() && st.empty();
    }

private:
    stack<int> st_sort;
    stack<int> st;
};
Share