1 介绍
本博客用来记录代码随想录leetcode200题之单调栈相关题目。
2 训练
题目1：739. 每日温度
解题思路：单调栈模型–找到数组中下一个更大数。从右到左遍历，保留更大值，因此是一个单调递减的栈。
C++代码如下，
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& a) {
int n = a.size();
vector<int> res(n, 0);
stack<int> stk;
for (int i = n-1; i >= 0; --i) {
while (!stk.empty() && a[stk.top()] <= a[i]) {
stk.pop();
}
if (!stk.empty()) {
res[i] = stk.top() - i;
}
stk.push(i);
}
return res;
}
};
python3代码如下，
class Solution:
def dailyTemperatures(self, a: List[int]) -> List[int]:
n = len(a)
stk = []
res = [0] * n
for i in range(n-1,-1,-1):
while len(stk) > 0 and a[stk[-1]] <= a[i]:
del stk[-1]
if len(stk) > 0:
res[i] = stk[-1] - i
stk.append(i)
return res
题目2：496. 下一个更大元素 I
解题思路：单调栈模型，数组中下一个更大的数。
C++代码如下，
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& a, vector<int>& b) {
int n = b.size();
stack<int> stk;
unordered_map<int, int> map_x_y;
for (int i = n-1; i >= 0; --i) {
while (!stk.empty() && b[stk.top()] <= b[i]) {
stk.pop();
}
if (!stk.empty()) {
map_x_y[b[i]] = b[stk.top()];
}
stk.push(i);
}
vector<int> res;
for (auto x : a) {
if (map_x_y.count(x) == 0) {
res.emplace_back(-1);
} else {
res.emplace_back(map_x_y[x]);
}
}
return res;
}
};
python3代码如下，
class Solution:
def nextGreaterElement(self, a: List[int], b: List[int]) -> List[int]:
n = len(b)
stk = []
map_x_y = collections.defaultdict(int)
for i in range(n-1,-1,-1):
while len(stk) > 0 and b[stk[-1]] <= b[i]:
del stk[-1]
if len(stk) > 0:
map_x_y[b[i]] = b[stk[-1]]
stk.append(i)
res = []
for x in a:
if x in map_x_y:
res.append(map_x_y[x])
else:
res.append(-1)
return res
题目3：503. 下一个更大元素 II
解题思路：数组中下一个更大的数。单调栈模型。
C++代码如下，
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> a;
for (auto x : nums) a.emplace_back(x);
for (auto x : nums) a.emplace_back(x);
int n = a.size();
stack<int> stk;
vector<int> res(n, -1);
for (int i = n-1; i >= 0; --i) {
while (!stk.empty() && a[stk.top()] <= a[i]) {
stk.pop();
}
if (!stk.empty()) {
res[i] = a[stk.top()];
}
stk.push(i);
}
res.erase(res.begin()+n/2, res.end());
return res;
}
};
python3代码如下，
class Solution:
def nextGreaterElements(self, a: List[int]) -> List[int]:
a += a
n = len(a)
stk = []
res = [-1] * n
for i in range(n-1,-1,-1):
while len(stk) > 0 and a[stk[-1]] <= a[i]:
del stk[-1]
if len(stk) > 0:
res[i] = a[stk[-1]]
stk.append(i)
return res[0:n//2]
题目4：42. 接雨水
解题思路：每一列的雨水高度，取决于，该列左侧最高的柱子和该列右侧最高的柱子，两者高度的较小值。
C++代码如下，
class Solution {
public:
int trap(vector<int>& a) {
int n = a.size();
vector<int> lmax(n, a[0]);
for (int i = 1; i < n; ++i) {
lmax[i] = max(a[i], lmax[i-1]);
}
vector<int> rmax(n, a.back());
for (int i = n-2; i >= 0; --i) {
rmax[i] = max(a[i], rmax[i+1]);
}
int res = 0;
for (int i = 0; i < n; ++i) {
res += min(lmax[i], rmax[i]) - a[i];
}
return res;
}
};
python3代码如下，
class Solution:
def trap(self, a: List[int]) -> int:
n = len(a)
lmax = [a[0]] * n
for i in range(1,n):
lmax[i] = max(a[i], lmax[i-1])
rmax = [a[-1]] * n
for i in range(n-2,-1,-1):
rmax[i] = max(a[i], rmax[i+1])
res = 0
for i in range(n):
res += min(lmax[i],rmax[i])-a[i]
return res
题目5：84. 柱状图中最大的矩形
解题思路：找到下一个更小的值。找到前一个更小的值。单调栈模型。
C++代码如下，
class Solution {
public:
int largestRectangleArea(vector<int>& a) {
int n = a.size();
//找到下一个更小的数
vector<int> rmin(n, n);
stack<int> stk;
for (int i = n-1; i >= 0; --i) {
while (!stk.empty() && a[stk.top()] >= a[i]) {
stk.pop();
}
if (!stk.empty()) {
rmin[i] = stk.top();
}
stk.push(i);
}
//找到前一个更小的数
vector<int> lmin(n,-1);
stk = stack<int>();
for (int i = 0; i < n; ++i) {
while (!stk.empty() && a[stk.top()] >= a[i]) {
stk.pop();
}
if (!stk.empty()) {
lmin[i] = stk.top();
}
stk.push(i);
}
//遍历求解答案
int res = 0;
for (int i = 0; i < n; ++i) {
int ans = a[i] * (rmin[i]-lmin[i]-1);
res = max(res, ans);
}
return res;
}
};
python3代码如下，
class Solution:
def largestRectangleArea(self, a: List[int]) -> int:
n = len(a)
#下一个更小的值
rmin = [n] * n
stk = []
for i in range(n-1,-1,-1):
while len(stk) > 0 and a[stk[-1]] >= a[i]:
del stk[-1]
if len(stk) > 0:
rmin[i] = stk[-1]
stk.append(i)
#前一个更小的值
lmin = [-1] * n
stk = []
for i in range(n):
while len(stk) > 0 and a[stk[-1]] >= a[i]:
del stk[-1]
if len(stk) > 0:
lmin[i] = stk[-1]
stk.append(i)
#计算答案
res = 0
for i in range(n):
ans = a[i] * (rmin[i] - lmin[i] - 1)
res = max(res, ans)
return res
文章评论