LeetCode-Day31——栈
636. 函数的独占时间
给出一个非抢占单线程CPU的 n 个函数运行日志，找到函数的独占时间。
每个函数都有一个唯一的 Id，从 0 到 n-1，函数可能会递归调用或者被其他函数调用。
日志是具有以下格式的字符串：function_id：start_or_end：timestamp。例如：“0:start:0” 表示函数 0 从 0 时刻开始运行。“0🔚0” 表示函数 0 在 0 时刻结束。
函数的独占时间定义是在该方法中花费的时间，调用其他函数花费的时间不算该函数的独占时间。你需要根据函数的 Id 有序地返回每个函数的独占时间。
示例 1:
1
2
3
4
5
6
7
8
| 输入:
n = 2
logs =
["0:start:0",
"1:start:2",
"1:end:5",
"0:end:6"]
输出:[3, 4]
|
说明：
1
2
3
4
5
6
7
8
9
10
11
| 函数 0 在时刻 0 开始，在执行了 2个时间单位结束于时刻 1。
现在函数 0 调用函数 1，函数 1 在时刻 2 开始，执行 4 个时间单位后结束于时刻 5。
函数 0 再次在时刻 6 开始执行，并在时刻 6 结束运行，从而执行了 1 个时间单位。
所以函数 0 总共的执行了 2 +1 =3 个时间单位，函数 1 总共执行了 4 个时间单位。
说明：
输入的日志会根据时间戳排序，而不是根据日志Id排序。
你的输出会根据函数Id排序，也就意味着你的输出数组中序号为 0 的元素相当于函数 0 的执行时间。
两个函数不会在同时开始或结束。
函数允许被递归调用，直到运行结束。
1 <= n <= 100
|
思路：
这里主要的问题就在于入栈和出栈的时间如何计算的问题
首先，res是我们要返回的独占时间的vector，然后st是存放还未出栈（即还未结束的程序）的pair<序号， 时间>
如果当前程序是start的，那么就先计算当前栈顶运行的时间(end - start)，加到res上去，然后再将当前程序压入栈
人如果当前程序是end的，那么需要先计算当前程序运行的时间，加到res上去，注意这里需要用(end - start + 1)。然后出栈，接着更新栈顶的时间为当前时间，这样就下一次匹配的时候就可以直接使用这边的时间作为start了。
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
| class Solution {
public:
vector<int> exclusiveTime(int n, vector<string>& logs) {
vector<int> res(n, 0);
stack<pair<int, int>> st;
for(string log: logs) {
istringstream ss(log);
string s1, s2, s3;
getline(ss, s1, ':');
getline(ss, s2, ':');
getline(ss, s3, ':');
int id = stoi(s1);
string action = s2;
int time = stoi(s3);
if(action == "start") {
if(!st.empty()) {
res[st.top().first] += (time - st.top().second);
}
st.push({id, time});
} else {
pair<int, int> p = st.top();
st.pop();
res[p.first] += (time - p.second + 1);
if(!st.empty()) {
st.top().second = time + 1;
}
}
}
return res;
}
};
|
Tips:
通过上述程序还可以了解一下istringstream的操作，以及stoi的方便的操作。
901. 股票价格跨度
编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。
今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。
示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。
注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。
|
思路：
本质上还是单调栈的应用
但是这里需要注意的是maxDay的计算（即连续第当前价格低的天数），这个需要累积，所以我的stack设计成pair<int, int>类型的，分别存放的是股票的价格以及前面连续有多少个比他低的天数（即有多少个比他小的数字被弹出栈）
那么新进来的股票价格就可以按照原先单调栈的思想进栈，但是需要累积maxDay（注意，这里的maxDay需要每新进入一个元素就需要计算）。
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
| class StockSpanner {
public:
vector<int> res;
vector<int> prices;
stack<pair<int, int>> st;
StockSpanner() {
}
int next(int price) {
prices.push_back(price);
if(st.empty()) {
st.push({price, 1});
} else if(st.top().first > price) {
st.push({price, 1});
} else {
int maxDay = 1;
while(!st.empty() && st.top().first <= price) {
maxDay += st.top().second;
st.pop();
}
st.push({price, maxDay});
}
return st.top().second;
}
};
|