普通栈
先进后出的特点
20. 有效的括号
class Solution {
public:
unordered_map<char, char> mp = {
{')', '('},
{']', '['},
{'}', '{'}
};
bool isValid(string s) {
stack<char> st;
for (char c : s) {
if (c == '(' || c == '[' || c == '{') {
st.push(c);
} else {
if (!st.empty() && mp[c] == st.top()) {
st.pop();
} else {
return false;
}
}
}
return st.empty();
}
};155. 最小栈
class MinStack {
private:
stack<int> xStack; // 存放正常数据
stack<int> minStack; // 顺序存放元素对应的最小值
public:
MinStack() {
}
void push(int val) {
xStack.push(val);
if (!minStack.empty()) {
minStack.push(min(minStack.top(), val));
} else {
minStack.push(val);
}
}
void pop() {
xStack.pop();
minStack.pop();
}
int top() {
return xStack.top();
}
int getMin() {
return minStack.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();
*/946. 验证栈序列
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
stack<int> st;
for (int i = 0, j = 0; i < pushed.size(); ++i) {
st.push(pushed[i]);
while (!st.empty() && st.top() == popped[j]) {
st.pop();
++j;
}
}
return st.empty();
}
};394. 字符串解码
class Solution {
public:
string getDigits(string& s, int& ptr) {
string res;
while (isdigit(s[ptr])) {
res.push_back(s[ptr++]);
}
return res;
}
string getString(vector<string> &v) {
string ret;
for (const auto &s: v) {
ret += s;
}
return ret;
}
string decodeString(string s) {
vector<string> stk;
int ptr = 0;
while (ptr < s.size()) {
char cur = s[ptr];
if (isdigit(cur)) {
string digits = getDigits(s, ptr);
stk.push_back(digits);
} else if (isalpha(cur) || cur == '[') {
stk.push_back(string(1, cur));
ptr++;
} else {
ptr++;
vector<string> sub;
while (stk.back() != "[") {
sub.push_back(stk.back());
stk.pop_back();
}
stk.pop_back();
int repTIme = stoi(stk.back());
stk.pop_back();
string subStr;
while (!sub.empty()) {
subStr += sub.back();
sub.pop_back();
}
string tmp;
while (repTIme--) {
tmp += subStr;
}
stk.push_back(tmp);
}
}
return getString(stk);
}
};单调栈
单调栈用途不太广泛，只处理一类典型的问题，比如「下一个更大元素」，「上一个更小元素」等。
739. 每日温度
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
// 单调递减栈，即从底到顶逐渐递减
stack<int> st;
vector<int> res(temperatures.size());
for (int i = 0; i< temperatures.size(); ++i) {
while (!st.empty() && temperatures[i] > temperatures[st.top()]) {
int preIndex = st.top();
res[preIndex] = i - preIndex;
st.pop();
}
st.push(i);
}
return res;
}
};496. 下一个更大元素 I
双数组
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
stack<int> st;
unordered_map<int, int> mp;
vector<int> res;
for (int i = 0; i < nums2.size(); ++i) {
while (!st.empty() && nums2[i] > st.top()) {
int preVal = st.top();
st.pop();
mp[preVal] = nums2[i];
}
st.push(nums2[i]);
}
for (auto num : nums1) {
if (mp.find(num) != mp.end()) {
res.push_back(mp[num]);
} else {
res.push_back(-1);
}
}
return res;
}
};503. 下一个更大元素 II
循环数组
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int len = nums.size();
stack<int> st;
vector<int> res(len, -1);
for (int i = 0; i < 2 * len; ++i) {
int index = i % len;
while (!st.empty() && nums[index] > nums[st.top()]) {
int preIndex= st.top();
st.pop();
res[preIndex] = nums[index];
}
st.push(index);
}
return res;
}
};84. 柱状图中最大的矩形
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int n = heights.size();
stack<int> st;
// 假设 h=heights[i]是矩形的高度，那么矩形的宽度最大是多少？我们需要知道：
// 1. 在 i 左侧的小于 h 的最近元素的下标 left
// 2. 在 i 右侧的小于 h 的最近元素的下标 right
vector<int> left(n, 0), right(n, n);
for (int i = 0; i < n; ++i) {
while (!st.empty() && heights[i] < heights[st.top()]) {
int index = st.top();
st.pop();
right[index] = i;
}
left[i] = st.empty() ? -1 : st.top();
st.push(i);
}
int res = 0;
for (int i = 0; i < n; ++i) {
int height = heights[i];
int wide = right[i] - left[i] - 1;
res = max(res, height * wide);
}
return res;
}
};42. 接雨水
单调栈解法：
【Leetcode每日打卡】接雨水问题的超完全手册 - 知乎 (zhihu.com)
class Solution {
public:
int trap(vector<int>& height) {
stack<int> st;
int res = 0;
for (int i = 0; i < height.size(); ++i) {
while (!st.empty() && height[i] > height[st.top()]) {
int bottomIndex = st.top();
st.pop();
while (!st.empty() && height[bottomIndex] == height[st.top()]) {
st.pop();
}
if (!st.empty()) {
int heightDiff = min(height[st.top()], height[i]) - height[bottomIndex];
int wide = i - st.top() - 1;
res += heightDiff * wide;
}
}
st.push(i);
}
return res;
}
};动态规划解法：找到第i个元素左右最大的值得较小值，减去当前高度，即为该列能存储的雨水
class Solution {
public:
int trap(vector<int>& height) {
int len = height.size();
int sum = 0;
vector<int> left_h(height.size());
vector<int> right_h(height.size());
for (int i = 1; i < len; ++i) {
left_h[i] = max(left_h[i-1], height[i-1]);
}
for (int j = len - 2; j >= 0; --j) {
right_h[j] = max(right_h[j+1], height[j+1]);
}
for (int i = 1; i < len - 1; ++i) {
int min_h = min(left_h[i], right_h[i]);
if (min_h > height[i]) {
sum += min_h - height[i];
}
}
return sum;
}
};双指针解法：
class Solution {
public:
int trap(vector<int>& height) {
int len = height.size();
int sum = 0;
int left = 0, right = len - 1;
int left_max = 0, right_max = 0;
while (left < right) {
if (height[left] < height[right]) {
if (left_max <= height[left]) {
left_max = height[left];
} else {
sum += left_max - height[left];
}
++left;
} else {
if (right_max <= height[right]) {
right_max = height[right];
} else {
sum += right_max - height[right];
}
--right;
}
}
return sum;
}
};