感觉二叉树每一题一个花样可能是因为栈和队列基础没打好，所以选择直接转入栈和队列。
想摆烂，煎熬----5/24
1.有效的括号
初版代码，有很多问题吧，正确的思路应该是把{ / [ / (压入栈，然后依次去匹配右边的括号
class Solution {
public:
bool isValid(string s) {
//妙的一点是网栈里加匹配的那半个，而不是原来的半个[感觉不能]
int size = s.size();
stack<char>st;
int i = 0;
while(i!=size){
if(!st.empty()){
char first = st.top();
// st.pop();
if(first == s[i]){
st.pop();
i++;
}else{
i++;
}
continue;//
}
// st.push(s[i]);//说好的放另一半
if(s[i]=='('){
st.push(')');
}else if(s[i]=='{'){
st.push('}');
}else if(s[i]=='['){
st.push(']');
}
i++;//
}//]]]
if(st.empty()){
return true;
}else{
return false;
}
}
};
混乱版本：【p.s.为了减少混乱其实可以for（），这样起码i++不会出错】
class Solution {
public:
bool isValid(string s) {
//妙的一点是往栈里加匹配的那半个，而不是原来的半个[感觉不能]
int size = s.size();
stack<char>st;
int i = 0;
while(i!=size){
if(s[i]=='('){
st.push(')');
}else if(s[i]=='{'){
st.push('}');
}else if(s[i]=='['){
st.push(']');
}else{//右括号
if(!st.empty()){
char first = st.top();
if(first == s[i]){
st.pop();
i++;//忘记了
continue;
}
}
return false;
}
i++;
}//]]]
if(st.empty()){
return true;
}else{
return false;
}
}
};2.最小栈5/24
本题的目标就是把求栈的min值从O(n)优化为O(1)
没思路
也是因为对C++类的不熟悉
class 类名 {
private: // 私有成员，只能被类内的成员函数访问 数据类型 成员变量;
public: // 公有成员，可以被类外部的代码访问
返回类型 成员函数(); // 成员函数声明
}; // 注意这里有分号
两个栈，一个放当前min数，
用一个栈存储min，空间换时间
class MinStack {//本题的目标就是用两个栈实现获得栈中元素min:O(n)变为O(1)
public:
stack<int> st;
stack<int>min;
MinStack() {
//常数时间内检索到最小元素的栈。
// min.push(1e9);
}
void push(int val) {
st.push(val);
if(min.empty() ||val < min.top()){
min.push(val);
}else{
min.push(min.top());
}
}
void pop() {//
st.pop();
min.pop();
}
int top() {
return st.top();
}
int getMin() {
return min.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(val);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->getMin();
*/3.字符串解码【没太理解】
乱了，感觉一个左括号需要一个stack
很难区分[[ ]]和 [ ][ ]
但是其实就是满足栈的情况，
难理解的是如何处理——
3[a2[c]]:3a先压入栈，然后2c压入栈，然后弹出
3[a]2[c]：3a先压入栈弹出，2c压入栈弹出
怎么保存之前的str和要输出的str
感觉用的是，过去的str是压在了栈，然后最后得到栈顶+当前循环的数组
？？？？？？？？？？？？——————————————————————————————？
迷惑：如何处理当前重复的和之前压入栈的
#include <stack>
#include <string>
using namespace std;
class Solution {
public:
string decodeString(string s) {
stack<int> numStack; // 存储重复次数
stack<string> strStack; // 存储外层字符串上下文
int currentNum = 0;
string currentStr = "";
for (char c : s) {
if (isdigit(c)) {
currentNum = currentNum * 10 + (c - '0');
} else if (c == '[') {
// 压入当前状态并重置
numStack.push(currentNum);
strStack.push(currentStr);
currentNum = 0;
currentStr = "";
} else if (c == ']') {
// 弹栈并生成重复字符串
int repeat = numStack.top();
numStack.pop();
string outerStr = strStack.top();
strStack.pop();
string temp;
for (int i = 0; i < repeat; ++i) {
temp += currentStr;
}
currentStr = outerStr + temp; // 栈顶+当前要重复的==总要重复的
} else {
currentStr += c;
}
}
return currentStr; // 最终结果在此
}
};4.每日温度【没太理解】
没思路，暴力O(n^2)
很奇妙，
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
//answer[i] 是指对于第 i 天，下一个更高温度出现在几天后
//暴力O(n……2)
//从右到左
stack<int>st;
vector<int>result(temperatures.size());
for(int i = temperatures.size()-1;i>=0;i--){
if(i==temperatures.size()-1){
result[i] = 0;
st.push(i);
}
int topNum = st.top();
if(temperatures[topNum] > temperatures[i]){
result[i] = topNum-i;
st.push(i);
}else{
// st.pop();
// st.push(i);
// result[i] = 0;
while(!st.empty()){
topNum = st.top();//没更新
if(temperatures[topNum] <= temperatures[i]){
st.pop();
}else{
result[i] = topNum-i;
break;
}
}
st.push(i);
}
}
return result;
}
};
没太理解从左往右