【有效括号】
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
思路：
遇到左括号入栈，遇到右括号弹一个出来看是否匹配，全部走完看栈里是否还有没配对的左括号，如果以上步骤中任意时刻出问题，直接返回false，都没出问题则返回true。
class Solution {
public:
bool isValid(string s) {
vector<char> stk;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
stk.push_back(s[i]);
}
if (s[i] == ')') {
if (stk.empty()||stk.back() != '(' )
return false;
stk.pop_back();
}
if (s[i] == '}') {
if (stk.empty()||stk.back() != '{')
return false;
stk.pop_back();
}
if (s[i] == ']') {
if (stk.empty()||stk.back() != '[')
return false;
stk.pop_back();
}
}
return stk.empty();
}
};【最小栈】
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()初始化堆栈对象。void push(int val)将元素val推入堆栈。void pop()删除堆栈顶部的元素。int top()获取堆栈顶部的元素。int getMin()获取堆栈中的最小元素。
思路：
对于栈中任意元素，在它出栈前，比它更靠近栈底的元素是不可能发生变化的，那么我们使用一个辅助栈，记录当前元素及其下方所有元素中的最小值即可。
class MinStack {
public:
stack<int> stk;
stack<int> stk_min;
MinStack() { stk_min.push(INT_MAX); }
void push(int val) {
stk.push(val);
if (val < stk_min.top())
stk_min.push(val);
else
stk_min.push(stk_min.top());
}
void pop() {
if (!stk.empty()) {
stk.pop();
stk_min.pop();
}
}
int top() { return stk.top(); }
int getMin() { return stk_min.top(); }
};【字符串解码】
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
思路：
我们可以把每一对括号想象成一个递归函数的调用和返回，遇到左括号=一个新的调用，因此要把当前的“现场”保存下来，然后先去进行内层函数的计算，遇到右括号=内层函数返回，返回的时候要把之前保存的“现场”恢复，继续进行外层函数的计算。我们用一个栈来模拟现场的保存和恢复。
class Solution {
public:
string decodeString(string s) {
stack<int> numStk;
stack<string> strStk;
int num = 0;
string cur = "";
for (int i = 0; i < s.size(); i++) {
//数字
if (s[i] >= '0' && s[i] <= '9') {
num = num * 10 + (s[i] - '0');
}
//括号
else if (s[i] == '[') {
numStk.push(num);
num = 0;
strStk.push(cur);
cur = "";
} else if (s[i] == ']') {
int n = numStk.top();
numStk.pop();
string temp = strStk.top();
strStk.pop();
for(int i=0;i<n;i++) {
temp += cur;
}
cur = temp;
}
//字母
else {
cur += s[i];
}
}
return cur;
}
};【每日温度】
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
【柱状图最大矩形】
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
思路：
第一题的思路就是第二题思路的一部分，就放在一起讲了。
对第一题来说，要找的是比自身大的，因此在遍历时，遇到小的先存起来，只有当前元素比栈顶下标元素大时，才开始弹出栈内下标，直到栈内没有比当前元素更大的数时停止，并把当前元素入栈。第一题做到这里就够了，因为对任意元素我们只需要考虑它后面的元素，而最后留在栈内的元素就是没有合法的后续元素的，标0就可以。
第二题的逻辑和第一题相同，只是评判条件和第一题相反，因为要找的是第一个小于当前元素的，找到它就找到了当前矩形的右边界，而栈内元素是递增的，左边界就是栈顶元素下面的元素（其实不一定，可能会有非严格递增的情况，也就是栈顶和它下面的元素一样大，但因为本题找的是最大值，这样做对结果不会有影响，所以就不单独拿出来讨论了）。然后对最后剩余元素的处理不太一样，他们延伸出的矩形一直到数组边界都是合法的，所以我们把数组边界作为它的右边界来做计算，左边界的选取方法不变。
class Solution
{
public:
vector<int> dailyTemperatures(vector<int>& temperatures)
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n=temperatures.size();
vector<int> st(n,0);
vector<int> ans(n,0);
int j=0;
for(int i=0;i<n;i++)
{
while((j > 0) && temperatures[st[j]] < temperatures[i])
{
ans[st[j]]=i-st[j];
j--;
}
j++;
st[j]=i;
}
return ans;
}
};class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
if (!heights.size())
return 0;
stack<int> stk;
stk.push(-1);
int maxArea = 0;
int l = 0, r = 0, curHeight = 0, curArea = 0;
for (int i = 0; i < heights.size(); i++) {
//空栈或能延伸
if (stk.top() == -1 || heights[i] >= heights[stk.top()]) {
stk.push(i);
continue;
}
//把能确定面积的都算了并退栈
while (stk.top() != -1 && heights[i] < heights[stk.top()]) {
curHeight = heights[stk.top()];
stk.pop();
curArea = (i - stk.top() - 1) * curHeight;
maxArea = max(maxArea, curArea);
}
stk.push(i);
}
//处理还没能出栈的
//还有
while (stk.top() != -1) {
curHeight = heights[stk.top()];
stk.pop();
curArea = (heights.size() - stk.top() - 1) * curHeight;
maxArea = max(maxArea, curArea);
}
return maxArea;
}
};
