LeetCode hot100---栈专题(C++语言)

1、有效的括号

（1）题目描述以及输入输出

(1)题目描述:
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

 
(2)输入输出描述：
输入：s = "()"
输出：true

关键思路：
遍历字符串，如果是左括号就将对应的右括号入栈
如果是右括号，假如栈为空或者与栈顶元素不匹配，则认为不匹配，否则出战匹配成功
遍历完，栈为空则匹配

（2）代码块

class Solution {
public:
    bool isValid(string s) 
    {
        stack<int> sta;
        if (s.size() % 2 != 0)              // 有奇数个括号肯定不匹配
            return false; 
        for(int i = 0;i < s.size();i++)
        {
            if(s[i] == '(')
                sta.push(')');
            else if(s[i] == '[')
                sta.push(']');
            else if(s[i] == '{')    
                sta.push('}');                          // 左括号匹配完成

            else if(sta.empty() || s[i] != sta.top())   // 不匹配的两种情况
                return false;
            else                                        // 括号匹配栈顶元素出栈
                sta.pop();
        }
        return sta.empty();                             // 括号匹配之后判断栈内是否为空
    }
};

2、字符串解码

（1）题目描述以及输入输出

(1)题目描述:
给定一个经过编码的字符串，返回它解码后的字符串。
 
(2)输入输出描述：
输入：s = "3[a]2[bc]"
输出："aaabcbc"

关键思路：
(1)碰到数字，num记录
(2)碰到字符，res记录
(3)碰到‘[’,num和res进栈
(4)碰到‘]’,取出栈顶数字，将res以倍数形式追加到栈顶字符串

（2）代码块

class Solution {
public:
    string decodeString(string s) 
    {
        int num = 0;        // 记录每次遍历的数字
        string res = "";    // 记录每次遍历的字符
        stack<int> nums;    // 数字栈
        stack<string> str;  // 字符栈

        for(int i = 0;i<s.size();i++)
        {
            if(s[i] >= '0' && s[i] <= '9')
                num =  s[i] - '0';

            else if((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z'))
                res = res + s[i];
            else if(s[i] == '[')
            {
                nums.push(num);
                num = 0;
                str.push(res);
                res  = "";
            }
            else if(s[i] == ']')
            {
                int times = nums.top();
                nums.pop();
                for(int i = 0;i<times;i++)
                {
                    str.top() += res;
                }
                res = str.top();
                str.pop();
            }
        }
        return res;
    }
};

3、每日温度

（1）题目描述以及输入输出

(1)题目描述:
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
 
(2)输入输出描述：
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

关键思路：
暴力循环

（2）代码块

#include <vector>

class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& temperatures) 
    {
        int n = temperatures.size();
        vector<int> result(n, 0); 			// 初始化结果向量，大小与输入相同，初始值为0

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (temperatures[j] > temperatures[i]) {
                    // 计算等待的天数
                    result[i] = j - i;
                    break; // 找到后可以跳出内层循环
                }
            }
        }
        
        return result; // 返回结果向量
    }
};