栈问题-LeetCode 155、42（最小栈问题）
作者：TeddyZhang
栈问题：LeetCode #155 #42
1
编程题
【LeetCode #155】最小栈
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
- push(x) -- 将元素 x 推入栈中。
- pop() -- 删除栈顶的元素。
- top() -- 获取栈顶元素。
- getMin() -- 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.
解题思路：
一个很简单的方法就是使用"双栈思想"，第一个栈为pushS，用于保存压入MinStack对象中的数据，而minS为储存各个阶段的最小值，并按照大小顺序进行排列。 假设压栈顺序为：5,4,1,1,6,7,2 则pushS的入栈顺序为：5,4,1,1,6,7,2 minS的入栈顺序为：5,4,1,1 其中注意一个问题，minS中的顺序是单调不增的，如果最小值为1，如果再压入一个值还是1的话，minS中也要压入一个数值为1.
class MinStack {
public:
/** initialize your data structure here. */
stack<int> minS;
stack<int> pushS;
MinStack() {
}
void push(int x) {
pushS.push(x);
if(minS.empty() || x <= minS.top()){
minS.push(x);
}
}
void pop() {
if(minS.top() == pushS.top()){
minS.pop();
}
pushS.pop();
}
int top() {
return pushS.top();
}
int getMin() {
return minS.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->getMin();
*/
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/min-stack
【LeetCode #42】接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6
解题思路：
首先我们定义left[i]表示i左边的最大值，right[i]表示i右边的最大值，并且两个数组初始化均为零。接着我们遍历整个数组，对于每一个位置i都获取其左右两边的最大值，并比较获取最小的数为level，也就是说没有柱子的话，雨水的高度为level. 从而实际对于i来说收集的雨水为level-height[i] ！！！
class Solution {
public:
int trap(vector<int>& height) {
int n = height.size();
// left[i]表示i左边的最大值，right[i]表示i右边的最大值
vector<int> left(n), right(n);
for (int i = ; i < n; i++) {
left[i] = max(left[i - ], height[i - ]);
}
for (int i = n - ; i >= ; i--) {
right[i] = max(right[i + ], height[i + ]);
}
int water = ;
for (int i = ; i < n; i++) {
int level = min(left[i], right[i]);
water += max(, level - height[i]);
}
return water;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/trapping-rain-water
腾讯云开发者
