- 30.包括min函数的栈
- 09.用两个栈实现队列
- 剑指 Offer II 036. 后缀表达式（逆波兰式）">剑指 Offer II 036. 后缀表达式（逆波兰式）
- 剑指 Offer II 037. 小行星碰撞">剑指 Offer II 037. 小行星碰撞
- 单调栈
- 剑指 Offer II 038. 每日温度（单调栈）">剑指 Offer II 038. 每日温度（单调栈）
- 剑指 Offer II 039. 直方图最大矩形面积（hard）">剑指 Offer II 039. 直方图最大矩形面积（hard）
- 剑指 Offer II 040. 矩阵中最大的矩形（重点）">剑指 Offer II 040. 矩阵中最大的矩形（重点）
30.包括min函数的栈
核心在于用另一个栈来保存当前栈的最小值，并且另一个栈顶始终是最小值，顺序按照原始栈的顺序来。
class MinStack {public:stack<int> stack1, stack2;/** initialize your data structure here. */MinStack() {while(!stack1.empty()){stack1.pop();}while(!stack2.empty()){stack2.pop();}}void push(int x) {if(stack2.empty()||stack2.top() >= x){stack2.push(x);}stack1.push(x);}void pop() {if(stack1.top() == stack2.top()){stack2.pop();}stack1.pop();}int top() {return stack1.top();}int min() {return stack2.top();}};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(x);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->min();*/
09.用两个栈实现队列
核心在于出现delete操作时就将两个栈倒装一次。保持队列的形式，只有当用于倒装的栈为空时，出现delete操作就会再次倒装。
class CQueue {
stack<int> stack1,stack2;
public:
CQueue() {
while(!stack1.empty()){
stack1.pop();
}
while(!stack2.empty()){
stack2.pop();
}
}//这个构造函数的作用就是清空两个栈
void appendTail(int value) {
stack1.push(value);
}
int deleteHead() {
// 如果第二个栈为空
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.top());
stack1.pop();
}
}
if (stack2.empty()) {
return -1;
} else {
int deleteItem = stack2.top();
stack2.pop();
return deleteItem;
}
}
};
剑指 Offer II 036. 后缀表达式（逆波兰式）
意思就是把运算符放在后面
- 使用栈来实现
- switch不能判断字符串
class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> stk; for(int i = 0; i < tokens.size(); i++){ string a = tokens[i]; if(isdigit(a[0])||isdigit(a[1])){ stk.push(stoi(tokens[i])); } else { int num1 = stk.top(); stk.pop(); int num2 = stk.top(); stk.pop(); switch (a[0]){ case '*': num1 = num1*num2;break; case '+': num1 = num1+num2;break; case '-': num1 = num2-num1;break; case '/': num1 = num2/num1;break; } stk.push(num1); } } return stk.top(); } };
剑指 Offer II 037. 小行星碰撞
就是情况有点多。
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
stack<int> stk;
for(int i = 0; i < asteroids.size(); i++){
if(stk.empty()||asteroids[i]>0) {
stk.push(asteroids[i]);
} else {
while(!stk.empty()&&stk.top() > 0&&abs(stk.top())<abs(asteroids[i])){
stk.pop();
}
if(stk.empty()||stk.top()<0) {
stk.push(asteroids[i]);
} else if(abs(stk.top()) == abs(asteroids[i])) stk.pop();
}
}
vector<int> res;
while(!stk.empty()) {
res.push_back(stk.top());
stk.pop();
}
reverse(res.begin(), res.end());
return res;
}
};
单调栈
剑指 Offer II 038. 每日温度（单调栈）
可以维护一个存储下标的单调栈，从栈底到栈顶的下标对应的温度列表中的温度依次递减。如果一个下标在单调栈里，则表示尚未找到下一次温度更高的下标。
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int n = temperatures.size();
stack<int> stk;
vector<int> res(n);
for(int i = 0; i < n; i++){
while(!stk.empty()){
int pre = stk.top();
if(temperatures[pre]>=temperatures[i]){
break;
}
res[pre] = i - pre;
stk.pop();
}
stk.push(i);
}
return res;
}
};
剑指 Offer II 039. 直方图最大矩形面积（hard）
- 注意单调栈存储的是下标
- 每个栈顶下标都代表这当前的高度
- 每当一个元素高度小于当前栈顶就代表找到了栈顶高度的右测，而因为栈是从小到大单调的，因此左侧也比较容易找到，就是当前栈顶的前一个元素（也就是当前栈顶pop之后的新的栈顶）。
- 遇到比栈顶元素小的元素，不是算以当前元素为顶的矩形面积，而是算以栈顶元素为顶的矩形面积。有点反直觉。
归纳一下枚举高的方法：
- 首先我们枚举某一根柱子i作为高h
- 随后我们需要向两边扩展，使得扩展的柱子高度均不小于h。换句话说我们需要找到找到左右两侧最近的高度小于h的柱子。
但是如果有两根柱子0和1，其中0在1的左侧，并且0的高度大于等于1，那么在后面的柱子i向左找小于其高度的柱子时，1会挡住0,0就不会作为答案了。
class Solution { public: int largestRectangleArea(vector<int>& heights) { stack<int> st;//单调栈是逐渐增大的，后入栈的应该都比前面的高度大。 //千万注意，单调栈存储的是下标 st.push(-1);//设置左墙壁 int n =heights.size(); int ans =0; for(int i=0;i<n;i++){ while(st.top()!=-1 && heights[st.top()]>=heights[i]){//循环维持栈的单调性 //计算过以栈顶元素的高之后，就pop出来 int tem = st.top(); st.pop(); //同11. 盛最多水的容器 一样高度减少 但是宽度增加 还是要比较面积大小 int curArea = heights[tem]*(i-st.top()-1);//当-1作为左端时，宽度实际上就是右端的下标 ans = max(ans,curArea); } st.push(i); } //此时的栈顶高度，索引后面的都比他大，索引前面的在栈中都比他小，因此右端为n，左端为新的栈顶。 while(st.top()!=-1){ int tem = st.top(); st.pop(); int curArea = heights[tem]*(n-st.top()-1); ans=max(ans,curArea); } return ans; } };剑指 Offer II 040. 矩阵中最大的矩形（重点）
这题就是上一题的加强版本
需要提前算出的左端最长连续个数
- 用这个i条件来作为单调栈建立的标准
- heights表示当前行的每个位置的从上到下连续为1的次数
后面的内容和上题类似，知道了每一列的连续1的次数，就相当于前面知道了高度。然后求建筑的最大面积。这里注意，行是会一直变化的，也就是说这一题的矩阵是可以不靠着x轴的，对应上一题也就是说建筑是可以悬空的。因此需要枚举每一行
class Solution { public: int maximalRectangle(vector<string>& matrix) { int n = matrix.size(); if(n == 0) return 0; int ans = 0; vector<int> heights(matrix[0].size()); //这里的这个可以通过类似dp的方法得到 //这里还进行了状态压缩 for(string row : matrix){//提前得到左端的最长连续1个数 for(int i = 0; i < row.size(); i++){ heights[i] = row[i] == '0' ? 0 : heights[i] + 1; } ans = max(ans, maximalRectangle(heights)); } return ans; } int maximalRectangle(vector<int>& heights){ int n = heights.size(); int ans = 0; stack<int> s; s.push(-1);// 防空 //后面的部分就和直方图最大矩形类似了 for(int i = 0; i < n; i++){//栈是从小到大，当遇到小于栈顶的情况时，就找到了以当前栈顶为宽度的情况。此时前后都小于它 //这一部分是每一列的情况 while(s.top() != -1 && heights[s.top()] >= heights[i]){ int tp = s.top(); s.pop(); ans = max(ans, heights[tp] * (i - s.top() - 1));//下端-上端-1 } s.push(i); } //栈中剩下来的元素都比后面的小，因此下端默认为n了 while(s.top() != -1){ int tp = s.top(); s.pop(); ans = max(ans, heights[tp] * (n - s.top() - 1)); } return ans; } };
若有收获，就点个赞吧
0 人点赞
