2019-12-12 刷题-3（栈）

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.整数（一轮的得分）：直接表示您在本轮中获得的积分数。

2. "+"（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。

3. "D"（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。

4. "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;
    }
};