算法数据结构

对顶栈

字数统计: 1.5k字   |   阅读时长: 6分
, ,

摘要: 对顶栈的使用场景

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

$1 场景

有一个光标，给出对光标的操作序列，维护操作结果，当操作有以下特性时，对顶栈可以很好地解决。

  • 一次只移动一位
  • 添加、删除均在光标操作
  • 操作位置一定在光标左右

对顶栈实现

1
2
vector<int> st_l;  // 左栈数据，光标在左栈栈顶
vector<int> st_r;  // 右栈数据

$2 题目

1472. 设计浏览器历史记录

你有一个只支持单个标签页的 浏览器 ，最开始你浏览的网页是 homepage ，你可以访问其他的网站 url ，也可以在浏览历史中后退 steps 步或前进 steps 步。

请你实现 BrowserHistory 类：

  • BrowserHistory(string homepage) ，用 homepage 初始化浏览器类。
  • void visit(string url) 从当前页跳转访问 url 对应的页面 。执行此操作会把浏览历史前进的记录全部删除。
  • string back(int steps) 在浏览历史中后退 steps 步。如果你只能在浏览历史中后退至多 x 步且 steps > x ，那么你只后退 x 步。请返回后退 至多 steps 步以后的 url 。
  • string forward(int steps) 在浏览历史中前进 steps 步。如果你只能在浏览历史中前进至多 x 步且 steps > x ，那么你只前进 x 步。请返回前进 至多 steps步以后的 url 。

提示：

1
2
3
4
5
1 <= homepage.length <= 20
1 <= url.length <= 20
1 <= steps <= 100
homepage 和 url 都只包含 '.' 或者小写英文字母。
最多调用 5000 次 visit， back 和 forward 函数。

示例：
输入：
[“BrowserHistory”,”visit”,”visit”,”visit”,”back”,”back”,”forward”,”visit”,”forward”,”back”,”back”]
[[“leetcode.com”],[“google.com”],[“facebook.com”],[“youtube.com”],[1],[1],[1],[“linkedin.com”],[2],[2],[7]]
输出：
[null,null,null,null,”facebook.com”,”google.com”,”facebook.com”,null,”linkedin.com”,”google.com”,”leetcode.com”]
解释：
BrowserHistory browserHistory = new BrowserHistory(“leetcode.com”);
browserHistory.visit(“google.com”); // 你原本在浏览 “leetcode.com” 。访问 “google.com”
browserHistory.visit(“facebook.com”); // 你原本在浏览 “google.com” 。访问 “facebook.com”
browserHistory.visit(“youtube.com”); // 你原本在浏览 “facebook.com” 。访问 “youtube.com”
browserHistory.back(1); // 你原本在浏览 “youtube.com” ，后退到 “facebook.com” 并返回 “facebook.com”
browserHistory.back(1); // 你原本在浏览 “facebook.com” ，后退到 “google.com” 并返回 “google.com”
browserHistory.forward(1); // 你原本在浏览 “google.com” ，前进到 “facebook.com” 并返回 “facebook.com”
browserHistory.visit(“linkedin.com”); // 你原本在浏览 “facebook.com” 。 访问 “linkedin.com”
browserHistory.forward(2); // 你原本在浏览 “linkedin.com” ，你无法前进任何步数。
browserHistory.back(2); // 你原本在浏览 “linkedin.com” ，后退两步依次先到 “facebook.com” ，然后到 “google.com” ，并返回 “google.com”
browserHistory.back(7); // 你原本在浏览 “google.com”， 你只能后退一步到 “leetcode.com” ，并返回 “leetcode.com”

算法：对顶栈

当前页面相当于光标，有以下几种操作：

  • 在光标处添加
  • 光标左移
  • 光标右移

由于不涉及删除光标处的操作，以及在光标处添加时，右栈的内容均失效，因此可以将对顶栈维护在一个数组里。

代码 (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
class BrowserHistory {
public:
    BrowserHistory(string homepage) {
        cache = vector<string>({homepage});
        pos = 0;
        max_pos = pos;
    }

    void visit(string url) {
        cache.erase(cache.begin() + pos + 1, cache.end());
        cache.push_back(url);
        ++pos;
        max_pos = pos;
    }

    string back(int steps) {
        if(pos - steps >= 0)
            pos -= steps;
        else
            pos = 0;
        return cache[pos];
    }

    string forward(int steps) {
        if(pos + steps <= max_pos)
            pos += steps;
        else
            pos = max_pos;
        return cache[pos];
    }

private:
    vector<string> cache;
    int pos;
    int max_pos;
};

128. 编辑器

问题

实现一个整数序列编辑器。

在开始时，序列是空的。

编辑器共有五种指令，如下：

1、“I x”，在光标处插入数值x。
2、“D”，将光标前面的第一个元素删除，如果前面没有元素，则忽略此操作。
3、“L”，将光标向左移动，跳过一个元素，如果左边没有元素，则忽略此操作。
4、“R”，将光标向右移动，跳过一个元素，如果右边没有元素，则忽略次操作。
5、“Q k”，假设此刻光标之前的序列为a1,a2,…,an,输出max1≤i≤kSi，其中Si=a1+a2+…+ai。

算法：对顶栈

光标的操作：

  • 光标处插入
  • 光标处删除
  • 光标左移
  • 光标右移
  • 光标左边元素的最大前缀和

前四个都是对顶栈的标准操作。第五个操作需要额外维护一个前缀和数组 sums 和最大前缀和数组 max_sums

1
2
sums[i] := [0..i] 的前缀和
max_sums[i] := [0..i] 的最大前缀和

每当光标处插入以及光标右移时，更新前缀和数组以及最大前缀和数组。即左栈进入元素的时候，更新两个数组。

代码 (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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <vector>
#include <iostream>

using namespace std;

int main()
{
    int Q;
    cin >> Q;
    vector<int> st_l, st_r;
    vector<int> sums;
    vector<int> max_sums;
    for(int i = 0; i < Q; ++i)
    {
        char s;
        cin >> s;
        if(s == 'I')
        {
            int x;
            cin >> x;
            st_l.push_back(x);
            int cur = st_l.size() - 1;
            // sums[cur], max_sums[cur]
            if((int)sums.size() - 1 < cur)
            {
                sums.push_back(st_l[cur]);
                max_sums.push_back(sums[cur]);
            }
            sums[cur] = st_l[cur];
            if(cur > 0)
                sums[cur] += sums[cur - 1];
            max_sums[cur] = sums[cur];
            if(cur > 0)
                max_sums[cur] = max(sums[cur], max_sums[cur - 1]);
        }
        else if(s == 'D')
        {
            if(!st_l.empty())
                st_l.pop_back();
        }
        else if(s == 'L')
        {
            if(!st_l.empty())
            {
                st_r.push_back(st_l.back());
                st_l.pop_back();
            }
        }
        else if(s == 'R')
        {
            if(!st_r.empty())
            {
                st_l.push_back(st_r.back());
                st_r.pop_back();
                int cur = st_l.size() - 1;
                if((int)sums.size() - 1 < cur)
                {
                    sums.push_back(st_l[cur]);
                    max_sums.push_back(sums[cur]);
                }
                sums[cur] = st_l[cur];
                if(cur > 0)
                    sums[cur] += sums[cur - 1];
                max_sums[cur] = sums[cur];
                if(cur > 0)
                    max_sums[cur] = max(sums[cur], max_sums[cur - 1]);
            }
        }
        else
        {
            int k;
            cin >> k;
            cout << max_sums[k - 1] << endl;
        }
    }
}

idth=”100%” height=”667” scrolling=no></iframe>

Share