算法学习笔记-栈(stack)

原创

买唯送忧

修改于 2021-05-24 10:45:49

3820

修改于 2021-05-24 10:45:49

文章被收录于专栏：虚拟技术学习虚拟技术学习

一、栈在括号匹配上的应用

1、leetcode第20题：https://leetcode-cn.com/problems/valid-parentheses/

这一类括号的题目，基本上都是左括号进栈，右括号判断终止；

class Solution {
public:
    bool isValid(string s) {
        stack <char> st;
        st.push('#'); //可以不用判空
        for (auto c : s){
            if (c == '[' || c == '(' || c == '{'){
                st.push(c);
            }else if ((c == ')' && st.top() == '(') || (c == ']' && st.top() == '[') || (c == '}' && st.top() == '{')){
                st.pop();
            }else{
                st.push(c);
            }
        }
        if (st.size() == 1)return true;
        return false;
    }
};

2、leetcode第921题：https://leetcode-cn.com/problems/minimum-add-to-make-parentheses-valid/

这题跟上面的题目是一模一样的，最少添加就是有多少括号没有对象，，没有对象的括号都会留在栈中，有的都会出栈，所以就是求栈的大小；

class Solution {
public:
    int minAddToMakeValid(string s) {
        if (s.size() == 0)return 0;
        stack <char> st;
        st.push('#');
        for (auto c : s){
            if (c == '[' || c == '(' || c == '{'){
                st.push(c);
            }else if ((c == ')' && st.top() == '(') || (c == ']' && st.top() == '[') || (c == '}' && st.top() == '{')){
                st.pop();
            }else{
                st.push(c);
            }
        }
        return st.size() - 1;
    }
};

3、leetcode第1021题：https://leetcode-cn.com/problems/remove-outermost-parentheses/

这个题找最外层括号，直接上两例子：

(())=> (进栈， (进栈，)判断，(出栈, )判断，此时(出栈后栈大小为0，所以这括号就是最外层的括号，如果给这字符串编号：

也就是要把最外层括号里面的字符串截取出来：即截取：st.top() + 1 ~ i - 1;

class Solution {
public:
string removeOuterParentheses(string s) {
        string result = "";
        stack <int> st;
        for (int i = 0; i < s.size(); i ++){
           //判断栈的大小是不是0，来确定是不是最外层括号
            if (s[i] == '(')st.push(i);
            else if (s[i] == ')'){
                if (st.size() == 1){
                    result += s.substr(st.top() + 1, i - 1 - st.top());
                }
                st.pop();
            }
        }
        return result;
    }
};

二、熟练掌握push(),pop()操作

1、leetcode第71题：https://leetcode-cn.com/problems/simplify-path/

对于路径问题：首先通过分隔符/把各个字符串分开，然后一个一个讨论；

（1）//即：/与/之前是''，直接跳过即可

（2）/./即：/./之间是.，直接跳过即可

（3）/../即：如果是/home/../a，那么之后就为/a，然后/../前面没元素直接跳过即可；

class Solution {
public:
    string simplifyPath(string path) {
        stringstream is(path);
        vector <string> vec;
        string tmp, result = "/";
        while (getline(is, tmp, '/')){
            if (tmp == "." || tmp == "")continue;
            else if (tmp == ".." && vec.size() != 0){
                vec.pop_back();
            }else if (tmp == ".." && vec.size() == 0){
                continue;
            }else{
                vec.push_back(tmp);
            }
        }
        for (int i = 0; i < vec.size(); i++){
            if (i < vec.size() - 1){
                result += vec[i] + "/";
            }else{
                result += vec[i];
            }
        }
        return result;
    }
};

2、leetcode第150题：https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/

不需多说

class Solution {
public:
  stack <int> data;
    int getNum(string str){
        int sum = 0;
        for (int i = 0; i < str.size(); i ++){
            if (str[i] == '-')continue;
            sum = sum * 10 - '0' + str[i];
        }
        if (str[0] == '-')return -sum;
        return sum;
    }
    int calcu(int data1, string op, int data2){
        if (op == "+")return data1 + data2;
        if (op == "-")return data1 - data2;
        if (op == "*")return data1 * data2;
        if (op == "/")return data1 / data2;
        return 0;
    }
    int evalRPN(vector<string>& tokens) {
        int data1, data2;
        string op;
        for (auto c : tokens){
            if (c == "+" || c == "-" || c == "*" || c == "/"){
                data2 = data.top();
                data.pop();
                data1 = data.top();
                data.pop();
                data.push(calcu(data1, c, data2));
            }else{
                int num = getNum(c);
                data.push(num);
            }
        }
        return data.top();
    }
};

3、leetcode第155题：https://leetcode-cn.com/problems/min-stack/

class MinStack {
        stack<int> x_stack;
        stack<int> min_stack;
    public:
        MinStack() {
            min_stack.push(INT_MAX);
        }
        
        void push(int x) {
            x_stack.push(x);
            min_stack.push(min(min_stack.top(), x));
        }
        
        void pop() {
            x_stack.pop();
            min_stack.pop();
        }
        
        int top() {
            return x_stack.top();
        }
        
        int getMin() {
            return min_stack.top();
        }
    };

4、leetcode第224题：https://leetcode-cn.com/problems/basic-calculator/

通过栈保存当前符号类型即把题目看成一种累加：比如：-3+3 + 4 ==》 ans先加-3，再加3，再加4；右括号的话就把括号外面的符号进栈，如果括号外面是负号，那么括号里面负号就是正号，

class Solution {
public:
   int calculate(string s) {
        stack <int> st;
        int sum = 0, op = 1, ans = 0;
        st.push(op);
        for (auto c : s){
            if (c == ' ') continue;
            else if (c >= '0'){
                sum = sum * 10 - '0' + c;
            }else{
                ans += op * sum;
                sum = 0;
                if (c == '+')op = st.top();
                if (c == '-')op = -st.top();
                if (c == '(')st.push(op);
                if (c == ')')st.pop();
            }
        }
        return ans + op * sum;
    }
};

5、leetcode第225题：https://leetcode-cn.com/problems/implement-stack-using-queues/

队列实现栈：基本思路就是：一个队列存已经在队列中的，一个队列存新进入的数据，然后把先前的数据插入到新进入数据的后面

class MyStack {
    private:
        queue <int> que1;
        queue <int> que2;
    public:
        /** Initialize your data structure here. */
        MyStack() {

        }

        /** Push element x onto stack. */
        void push(int x) {
            que1.push(x);
            while (!que2.empty()){
                que1.push(que2.front());
                que2.pop();
            }
            swap (que1, que2);
        }

        /** Removes the element on top of the stack and returns that element. */
        int pop() {
            int num = que2.front();
            que2.pop();
            return num;
        }

        /** Get the top element. */
        int top() {
            return que2.front();
        }

        /** Returns whether the stack is empty. */
        bool empty() {
            return que2.empty();
        }
    };

6、leetcode第232题：https://leetcode-cn.com/problems/implement-queue-using-stacks/

用栈实现队列：一个栈输入，一个栈输出：插入数据进输入栈，如果输出数据，那就把输入栈的数据输出到输出栈，再从输出栈中输出，然后后续还需要输出数据，再从输出栈中查看，然后输出栈还有数据，那就直接出栈，否则，就把输入栈的数据输出到输出栈，再从输出栈中输出。

class MyQueue {
private:
    stack<int> inStack, outStack;

    void in2out() {
        while (!inStack.empty()) {
            outStack.push(inStack.top());
            inStack.pop();
        }
    }

public:
    MyQueue() {}

    void push(int x) {
        inStack.push(x);
    }

    int pop() {
        if (outStack.empty()) {
            in2out();
        }
        int x = outStack.top();
        outStack.pop();
        return x;
    }

    int peek() {
        if (outStack.empty()) {
            in2out();
        }
        return outStack.top();
    }

    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

7、leetcode第946题：https://leetcode-cn.com/problems/validate-stack-sequences/

验证这个序列是不是栈的出栈序列：这种题目的解法就是重现出栈场景，把数据一一入栈，在入栈的同时将其与给定的出栈序列比较，如果相同，那就把数据出栈，否则入栈，最后遍历完，如果栈为空，那就是出栈序列：

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
        stack <int> st;
        for (int i = 0; i < pushed.size(); i ++){
            st.push(pushed[i]);
            while (st.top() == popped[0]){
                st.pop();
                popped.erase(popped.begin(), ++popped.begin());
                if (st.empty())break;
            }
        }
        return st.empty();
    }
};

8、leetcode第1047题：https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/

class Solution {
public:
    string removeDuplicates(string s) {
        stack <char> st;
        st.push('#');
        for (auto c : s){
            if (c == st.top()){
                st.pop();
            }else{
                st.push(c);
            }
        }
        string str = "";
        while (st.top() != '#'){
            str += st.top();
            st.pop();
        }
        reverse(str.begin(), str.end());
        return str;
    }
};

三、栈在编码方面的应用

1、leetcode第394题：https://leetcode-cn.com/problems/decode-string/

通过[]入栈，来判断需要重复的字符，，通过栈内[之前的数字来决定次数：

class Solution {
public:
        string decodeString(string s) {
        stack <int> num;
        stack <char> st;
        string str = "", tmp;
        int ans = 0;
        for (auto c : s){
            if (c >= '0' && c <= '9'){
                ans = ans * 10 + c - '0';
            }else if (c == ']'){
                while (st.top() != '['){
                    tmp += st.top();
                    st.pop();
                }
                st.pop();
                reverse(tmp.begin(), tmp.end());
                for (int i = 0; i < num.top(); i ++){
                    str += tmp;
                }
               num.pop();
                for (auto v : str){
                    st.push(v);
                }
                str = tmp =  "";
            }else if (c == '['){
                num.push(ans);
                ans = 0;
                st.push(c);
            }else{
                st.push(c);
            }
        }
        while (!st.empty()){
            str += st.top();
            st.pop();
        }
        reverse(str.begin(), str.end());
        return str;
    }
};

2、leetcode第682题：https://leetcode-cn.com/problems/baseball-game/

class Solution {
public:
  int calPoints(vector<string>& ops) {
        stack <int> st;
        for (auto v : ops){
            if (v == "D"){
                st.push(st.top() * 2);
            }else if (v == "C"){
                st.pop();
            }else if (v == "+"){
                int data2 = st.top();
                st.pop();
                int data1 = st.top();
                st.pop();
                int data3 = data1 + data2;
                st.push(data1);
                st.push(data2);
                st.push(data3);
            }else{
                int num = 0;
                if (v[0] == '-'){
                    for (int i = 1; i < v.size(); i ++){
                        num = num * 10 + v[i] - '0';
                    }
                     st.push(-num);
                }else{
                    for (int i = 0; i < v.size(); i ++){
                        num = num * 10 + v[i] - '0';
                    }
                    st.push(num);
                }

            }
        }
        int data = 0;
        while (st.size() != 0){
            data += st.top();
            st.pop();
        }
        return data;
    }
};

3、leetcode第856题：https://leetcode-cn.com/problems/score-of-parentheses/

括号的分数：

（1）初始遇到(把0进栈；

（2）如果遇到)说明有完整的括号了，需要加分；

（3）怎么加分呢？若是栈顶为0，说明此时括号内无括号，栈顶的下一个表示前面并列的括号，也就是说，判断栈顶是否为0,0那么就加一，不是0，那么就在原有的基础是乘以2，之后再加上栈顶之后的；

class Solution {
public:
    int scoreOfParentheses(string s) {
        stack <int> st;
        st.push(0);
        for (auto c : s){
            if (c == '('){
                st.push(0);
            }else{
                int data1 = st.top();
                st.pop();
                int data2 = st.top();
                st.pop();
                st.push(max(1, 2 * data1) + data2);
            }
        }
        return st.top();
    }
};

4、leetcode第880题：https://leetcode-cn.com/problems/decoded-string-at-index/

class Solution {
public:
      string decodeAtIndex(string S, int K) {
        long long len = 0;
        int N = S.size();
        for (auto c : S){
            if (isdigit(c)){
                len *= c - '0';
            }else{
                len ++;
            }
        }
        for (int i = N - 1; i >= 0; i --){
            K %= len;
            if (K == 0 && isalpha(S[i]))
                return (string)"" + S[i];
            if (isdigit(S[i])){
                len /= S[i] - '0';
            }else{
                len --;
            }
        }
        return "";
    }
};

四、单调栈

1、leetcode第84题：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

像这种用单调栈解法解答的题目有个特点：就是类似于山峰，或者山谷；比如1 2 3 4 8 6，或者5 4 2 1 3；然后单调栈里一般存的是下标，这样更好的计算跨度。

对于这道题：2 1 5 6 2 3=》就是一种类似于山峰的：

（1）如果当前数比栈顶元素大，那么进栈，如果小，那就把栈顶元素出栈并且计算面积：

 class Solution {
    private:
        stack <int> st;
    public:
        int largestRectangleArea(vector<int> &heights)
        {
            int ans = 0;
            heights.insert(heights.begin(), 0);
            heights.push_back(0);
            st.push(0);
            for (int i = 1; i < heights.size(); i ++){
                while (heights[st.top()] > heights[i]){
                    int top = st.top();
                    st.pop();
                    int result = (i - st.top() - 1) * heights[top];
                    ans = max(ans, result);
                }
                st.push(i);
            }
            return ans;
        }
    };

2、leetcode第456题：https://leetcode-cn.com/problems/132-pattern/

题目都告诉你了：132模式，妥妥的山峰类型；但是这个加了一个条件就是山峰左边的数也要比右边小；

这个时候只要把左边的数或者右边的数记住，然后再进一个判断即可；

    class Solution {
    public:
        //3 1 4 2;
        bool find132pattern(vector<int>& nums) {
            stack<int> st;
            int n = nums.size(), k = INT_MIN;
            for(int i = n - 1; i >= 0; i--){
                if(nums[i] < k) return true;
                while(!st.empty() and st.top() < nums[i]) {
                    k = max(k,st.top()); st.pop();
                }
                st.push(nums[i]);
            }
            return false;
        }
    };

3、leetcode第496题：https://leetcode-cn.com/problems/next-greater-element-i/

class Solution {
    public:
        vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
            vector <int> result;
            int flag;
            for (auto c : nums1){
                flag = 0;
                auto x = ::find(nums2.begin(), nums2.end(), c);
                for (x + 1; x != nums2.end(); x ++){
                    if (*x > c){
                        flag = 1;
                        result.push_back(*x);
                        break;
                    }
                }
                if (flag == 0){
                    result.push_back(-1);
                }
            }
            return result;
        }
    };

4、leetcode第503题：https://leetcode-cn.com/problems/next-greater-element-ii/

这是山谷类型：比如3 2 1 4 5 7 6；很明显3 2 1 的下一个更大是4，也就是如果栈为空，或者当前元素小于栈顶元素，那么直接入栈，如果大于栈顶元素，那就把对应下标对应的值改成当前元素：

class Solution {
public:
         vector<int> nextGreaterElements(vector<int>& nums) {
        int n=nums.size();
        vector<int>res(n,-1);
        stack<int>stk;
        for (int i=0;i<n*2;i++)
        {
                while(!stk.empty()&&nums[i%n]>nums[stk.top()])
                {
                    int j=stk.top();
                    stk.pop();
                    res[j]=nums[i%n];
                }
                stk.push(i%n);  
        }
        return res;
    }
};

5、leetcode739：https://leetcode-cn.com/problems/daily-temperatures/

无需多说，跟上面题目差不多；

class Solution {
public:
 vector<int> dailyTemperatures(vector<int>& temperatures) {
        int n = temperatures.size();
        vector <int> res(n, 0);
        stack <int> st;
        //[73, 74, 75, 71, 69, 72, 76, 73]
        for (int i = 0; i < n; i ++){
            while (!st.empty() && temperatures[i] > temperatures[st.top()]){
                int cur = st.top();
                st.pop();
                res[cur] = i - cur;
            }
            st.push(i);
        }
        return res;
    }
};

6、leetcode901:https://leetcode-cn.com/problems/online-stock-span/

也是类似的，包括之后的；

class StockSpanner {
    public:
        StockSpanner() {
    
        }
        
        int next(int price) {
            int count = 0;
            while (!stk.empty() && price >= prices[stk.top()]) {
                stk.pop();
            }
            count = stk.empty() ? prices.size() + 1 : prices.size() - stk.top();
            prices.push_back(price);
            stk.push(prices.size() - 1);
            return count;
        }
    
    private:
        vector<int> prices;
        stack<int> stk;
    };

7、leetcode907：https://leetcode-cn.com/problems/sum-of-subarray-minimums/

对于这道题也是山谷类型： 4 5 6 3 7 8,3就是最小值，然后以他为最小值个数就是：3左边的数目加上3本身也就是m+1,类似的右边就是n + 1，总的个数就是3*(m + 1)(n+1);

也就是说当前元素比栈顶元素大，直接进栈，如果比其小，那么就要进行判断栈顶元素左右的个数；

class Solution {
public:
 const int MOD = 1e9 + 7;
    int sumSubarrayMins(vector<int>& arr) {
        arr.push_back(-1);
        int res = 0, len = arr.size();
        stack <int> st;
        for (int i = 0; i < len; i ++){
            while (!st.empty() && arr[i] <= arr[st.top()]){
                int index = st.top();
                st.pop();
                int prev = -1;
                if (!st.empty())prev = st.top();
                int left = index - prev;
                int right = i - index;
                res = (res + ((long)arr[index] * left * right) % MOD) % MOD;
            }
            st.push(i);
        }
        //3 1 2 4;
        return res;
    }
};

8、leetcode1019:https://leetcode-cn.com/problems/next-greater-node-in-linked-list/

 class Solution {
       
    public:
        vector<int> nextLargerNodes(ListNode* head) {
            int len = 0;
            stack <int> st;
            vector <int> nums;
            ListNode* p = head;
            while (p){
                nums.push_back(p->val);
                p = p->next;
            }
            len = nums.size();
            vector <int> vec(len, 0);
            for (int i = 0; i < len; i ++){
                while (!st.empty() && nums[i] > nums[st.top()]){
                    int index = st.top();
                    st.pop();
                    vec[index] = nums[i];
                }
                st.push(i);
            }
            return vec;
        }
    };

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

c++

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

c++

登录后参与评论

0 条评论

热度