Stack栈，是一种后进先出的数据结构，在进行递归的时候，很适合使用。这里总结了两篇Stack 1, Stack 2
stack，queue属于STL，但不是container，是属于container adapter。可以使用vector，list，deque实现。支持：
Push, pop, top, size, empty, swap.
可以使用其它的容器初始化：
std::stack<int, std::vector<int>> third;
std::stack<int, std::list<int>> third;
- Monotonic stack
// 42. Trapping Rain Water
// Ref: https://leetcode-cn.com/problems/trapping-rain-water/solution/42-jie-yu-shui-shuang-zhi-zhen-dong-tai-wguic/
int trap(vector<int>& heights) {
if (heights.empty()) return 0;
stack<int> record;
int count = 0;
for (int i = 0; i < heights.size(); ++i) {
while (!record.empty() && heights[i] >= heights[record.top()]) {
const int mid = record.top();
record.pop();
if (record.empty()) break;
const int left = record.top();
count += (min(heights[left], heights[i]) - heights[mid])*
(i - left - 1);
}
if(record.empty() || heights[record.top()] > heights[i]) {
record.push(i);
}
}
return count;
}
// 84. Largest Rectangle in Histogram
// Ref: https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/84-zhu-zhuang-tu-zhong-zui-da-de-ju-xing-6cb8/
// https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/bao-li-jie-fa-zhan-by-liweiwei1419/
// https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/xiang-jie-dan-diao-zhan-bi-xu-miao-dong-by-sweetie/
// https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/xiang-jie-dan-diao-zhan-bi-xu-miao-dong-by-sweetie/
// https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/xiang-xi-jie-shao-dan-diao-zhan-de-li-jie-he-shi-y/
int largestRectangleArea(vector<int>& heights) {
stack<int> record;
int max_area = 0;
heights.insert(heights.begin(), 0);
heights.emplace_back(0);
record.push(0);
for (int i = 1; i < heights.size(); ++i) {
while (heights[record.top()] > heights[i]) {
const int mid = record.top();
record.pop();
max_area = max(max_area, (i - record.top() - 1) * heights[mid]);
}
record.push(i);
}
return max_area;
}
// 85. Maximal Rectangle
// DP + brute force.
// Reference: https://leetcode-cn.com/problems/maximal-rectangle/solution/maximal-rectangle-by-ikaruga-idh2/
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
vector<vector<int>> mat(matrix.size() + 1, vector<int>(matrix[0].size() + 1, 0));
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[0].size(); ++j) {
mat[i+1][j+1] =
matrix[i][j] == '0'? 0:mat[i+1][j] + 1;
}
}
int max_area = 0;
for (int i = 1; i < mat.size(); ++i) {
for (int j = 1; j < mat[0].size(); ++j) {
int min_len = mat[i][j];
int cur_area = min_len;
int k = i - 1;
while (k > 0) {
if (!mat[k][j]) break;
min_len = min(min_len, mat[k][j]);
cur_area = max(cur_area, min_len * (i - k + 1));
--k;
}
max_area = max(max_area, cur_area);
}
}
return max_area;
}
// Monotonic stack.
int maximalRectangle(vector<vector<char>>& matrix) {
if (matrix.empty() || matrix[0].empty()) return 0;
vector<int> heights(matrix[0].size() + 2, 0);
int max_area = 0;
for (int i = 0; i < matrix.size(); ++i) {
for (int j = 0; j < matrix[0].size(); ++j) {
if (matrix[i][j] == '0') {
heights[j+1] = 0;
} else {
++heights[j+1];
}
}
max_area = max(max_area, MaxHistogramArea(heights));
}
return max_area;
}
int MaxHistogramArea(const vector<int>& heights) {
stack<int> record;
record.push(heights[0]);
int max_area = 0;
for (int i = 1; i < heights.size(); ++i) {
while (heights[record.top()] > heights[i]) {
const int mid = record.top();
record.pop();
max_area = max(max_area, heights[mid] * (i - record.top() - 1));
}
record.push(i);
}
return max_area;
}
// 316.
// 402.
// 496.
// 581.
// 739.
// 901.
// 1776. Car Fleet II
// https://leetcode-cn.com/problems/car-fleet-ii/solution/che-dui-ii-si-lu-tui-dao-zhan-de-ying-yo-jqym/
// 这里面最重要的逻辑转换就是如果没法追上右边第一辆的车，那么就是
vector<double> getCollisionTimes(vector<vector<int>>& cars) {
vector<double> ans(cars.size(), -1.0);
stack<int> record;
record.push(cars.size()-1);
for (int i = cars.size()-2; i >= 0; --i) {
while (!record.empty()) {
if (cars[record.top()][1] >= cars[i][1] ||
ans[record.top()] > 1e-7 && 1.0*(cars[record.top()][0] - cars[i][0]) >
(cars[i][1] - cars[record.top()][1])* ans[record.top()])
record.pop();
else break;
}
if (!record.empty()) {
ans[i] = 1.0*(cars[record.top()][0] - cars[i][0]) /
(cars[i][1] - cars[record.top()][1]);
}
record.push(i);
}
return ans;
}