对顶栈

  |  

摘要: 对顶栈的使用场景

【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的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