496-下一个更大元素
由于两个向量中所有元素都是不重复的，因此本题可以采取栈+哈希表来进行。抛开nums1不谈，只要扫描一遍nums2，就可以得到所有元素到下一个更大元素，存放到哈希表中的对应位置。得到每个元素的更大元素这一问题，属于延迟缓冲类型，将当前扫描到到每个元素先入栈，继续扫描下一个元素，如果大于栈顶元素，则栈顶元素可以出栈，否则当前元素入栈，等待比他大的元素出现；由此得到的栈内元素为降序排列。
时间复杂度：O(n)
代码：
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
map<int, int> next_map;
stack<int> cur_stack;
//construct hashmap <num, next_large>
for (int i = 0; i < nums2.size(); i++) {
int cur_num = nums2[i];
while (!cur_stack.empty()) {
if (cur_num > cur_stack.top()) {
next_map[cur_stack.top()] = cur_num;
cur_stack.pop();
}
else break;
}
cur_stack.push(cur_num);
}
while (!cur_stack.empty()) { // not found
next_map[cur_stack.top()] = -1;
cur_stack.pop();
}
// process nums1
vector<int> numsg;
for (int i = 0; i < nums1.size(); i++) {
int tmp = nums1[i];
numsg.push_back(next_map[tmp]);
}
return numsg;
}
};
682-棒球比赛
给定一个字符串列表，每个字符串可以是以下四种类型之一：
1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。
"+"（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。
"D"（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。
"C"（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效 回合的分数是无效的，应该被移除。
本题属于延迟缓冲，后面的操作可以影响前面的得分，所以需要将前面的分数先用栈缓冲起来，最后再求和。
比如["5","2","C","D","+"]
第一轮：| 5
第二轮：| 5 2
第三轮：前一轮分数出栈，当前栈为 | 5
第四轮：本轮得分为栈顶元素两倍，10入栈，当前栈为 |5 10
第五轮：本轮得分为栈顶两个元素之和，15入栈，当前栈为 | 5 10 15
最后将栈中元素相加。
代码：
时间：96.96%, 空间： 69.82%
class Solution {
public:
int calPoints(vector<string>& ops) {
stack<int> s_stack;
for (int i = 0; i < ops.size(); i++) {
string cur = ops[i];
int last, last1, last2;
switch (cur[0]) {
case 'C': // remove last
s_stack.pop();
break;
case 'D': // twice last
last = s_stack.top();
s_stack.push(last * 2);
break;
case '+': // add last two
last1 = s_stack.top();
s_stack.pop();
last2 = s_stack.top();
s_stack.push(last1);
s_stack.push(last1 + last2);
break;
default:
int cur_score = stoi(cur);
s_stack.push(cur_score);
}
}
int total_score = 0;
while (!s_stack.empty()) {
total_score += s_stack.top();
s_stack.pop();
}
return total_score;
}
};
844-比较含退格的字符串
- 解法一：最简单的做法就是维护两个栈，把退格消去，然后再做比较。
代码：
时间：77.02%， 空间：77.69%
class Solution {
public:
string recover_str(string s) {
stack<char> char_stack;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '#') {
if (!char_stack.empty())
char_stack.pop();
}
else
char_stack.push(s[i]);
}
string rec_str = "";
while (!char_stack.empty()) {
rec_str += char_stack.top();
char_stack.pop();
}
return rec_str;
}
bool backspaceCompare(string S, string T) {
string S_c = recover_str(S);
string T_c = recover_str(T);
return (S_c == T_c);
}
};
- 解法二：双指针法。
解法二不需要借助栈，空间占用比解法一小很多。设置两个指针，分别指向两个字符串的末尾，设置两个变量存放当前所剩的退格数。本题的条件判断很复杂，如果从内层while循环出来时如果指针没有指向-1，则该位置的字符串是无法消去的；而到外层循环的结尾，如果指针没有指向-1，则下一轮可以继续比较。
时间：77.09%， 空间：90.84%
class Solution {
public:
bool backspaceCompare(string S, string T) {
bool is_equal = true;
int counter_s = 0, counter_t = 0;
int i = S.size() - 1, j = T.size() - 1;
while (i >= 0 || j >= 0) {
while (i >= 0 && (S[i] == '#' || counter_s > 0)) {
if (S[i] == '#') {
counter_s++;
i--;
}
else { // counter_s > 0
i--;
counter_s--;
}
}
while (j >= 0 && (T[j] == '#' || counter_t > 0)) {
if (T[j] == '#') {
counter_t++;
j--;
}
else { // counter_s > 0
j--;
counter_t--;
}
}
// >=0 means the current char cannot be removed, while the other string come to the end
if ((i >= 0) != (j >= 0)) return false;
// both string has been cleared
if ((i < 0) && (j < 0)) return true;
// element not equal
if (S[i] != T[j]) return false;
// i >= 0, j >= 0;
i--;
j--;
}
return true;
}
};
