# 单调栈算法

2019-12-04 13:02 CST

2019-12-29 00:23 CST

## 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-最大矩形

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;
}
};