单调栈算法
(2019年12月04日)
用处
求数组左侧/右侧比更小/更大的第一个值
42-接雨水
不断找到左边第一个比当前低的柱子,计算宽度、高度差和体积并加到答案里
class Solution {
public:
int n;
stack<pair<int,int>> s;
int trap(vector<int>& h) {
n = h.size();
int ans = 0;
for (int i = 0; i < n; ++i) {
while (!s.empty() and h[i] > s.top().second) {
pair<int,int> p = s.top();
s.pop();
if (s.empty()) {
s.push(p);
break;
}
int x = i - s.top().first - 1;
int y = min(s.top().second, h[i]);
if (y < p.second) break;
ans += x * (y - p.second);
}
s.push(make_pair(i, h[i]));
}
while (!s.empty()) s.pop();
return ans;
}
};
84-柱状图中的最大矩形
问求老题目,找到每一个元素左边第一个比它小的元素(单调递增栈)。
class Solution {
public:
int n, ans;
stack<pair<int,int>> s;
int largestRectangleArea(vector<int>& heights) {
n = heights.size(), ans = 0;
heights.push_back(0);
s.push(make_pair(-1, 0));
for (int i = 0; i <= n; ++i) {
while (!s.empty() and heights[i] < s.top().second) {
int h = s.top().second;
s.pop();
ans = max(ans, h * (i - s.top().first - 1));
}
s.push(make_pair(i, heights[i]));
}
while (!s.empty()) s.pop();
return ans;
}
};
85-最大矩形
对行前缀和(?),然后每行求一次直方图中的最大矩形面积
也可以DP或者用位运算暴力。
class Solution {
public:
int m, n;
vector<int> h;
int solve() {
int ret = 0;
stack<pair<int, int>> s;
for (int i = 0; i < n; ++i) {
while (!s.empty() and h[i] < s.top().second) {
auto p = s.top();
s.pop();
int x = s.empty() ? i : (i - s.top().first - 1);
int y = p.second;
ret = max(ret, x * y);
}
s.push(make_pair(i, h[i]));
}
while (!s.empty()) {
auto p = s.top();
s.pop();
int x = s.empty() ? n : (n - s.top().first - 1);
int y = p.second;
ret = max(ret, x * y);
}
return ret;
}
int maximalRectangle(vector<vector<char>>& matrix) {
m = matrix.size();
if (m == 0) return 0;
n = matrix[0].size();
if (n == 0) return 0;
h.resize(n, 0);
int ans = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] == '1') ++h[j];
else h[j] = 0;
}
ans = max(ans, solve());
}
return ans;
}
};
962-最大宽度坡
对每个元素找到左侧第一个不比它小(大于等于)的元素(单调递减栈)。
class Solution {
public:
int n, ans;
stack<pair<int,int>> s;
int maxWidthRamp(vector<int>& A) {
n = A.size();
for (int i = 0; i < n; ++i) {
if (s.empty() or A[i] < s.top().second) {
s.push(make_pair(i, A[i]));
}
}
ans = 0;
for (int i = n-1; i >= 0; --i) {
while (!s.empty() and A[i] >= s.top().second) {
ans = max(ans, i - s.top().first);
s.pop();
}
}
return ans;
}
};
1124-表现良好的最长时间段
996福报题 转化为前缀和中对每个元素找到左侧第一个比它大的元素(单调递减栈)。
class Solution {
public:
int n;
vector<int> p;
stack<pair<int,int>> s;
int longestWPI(vector<int>& hours) {
n = hours.size();
p.resize(n+1, 0);
for (int i = 1; i <= n; ++i) {
p[i] = p[i-1] + (hours[i-1] > 8 ? 1 : -1);
}
for (int i = 0; i <= n; ++i) {
if (s.empty() or p[i] < s.top().second) {
s.push(make_pair(i, p[i]));
}
}
int ans = 0;
for (int i = n; i >= 1; --i) {
while (!s.empty() and p[i] > s.top().second) {
ans = max(ans, i - s.top().first);
s.pop();
}
}
return ans;
}
};