- 84. 柱状图中最大的矩形
- 907. 子数组的最小值之和
- 单调栈 + 贡献值
Leetcode
单调栈：分为单调递增栈和单调递减栈
1、如果新的元素比栈顶元素大，就入栈；
2、如果新的元素较小，那就一直把栈内元素弹出来，直到栈顶比新元素小。
3、栈内的元素是递增的
4、当元素出栈时，说明这个新元素是出栈元素向后找第一个比其小的元素
现在索引在 6 ，栈里是 1 5 6 。
接下来新元素是 2 ，那么 6 需要出栈。
当 6 出栈时，右边 2 代表是 6 右边第一个比 6 小的元素。
当元素出栈后，说明新栈顶元素是出栈元素向前找第一个比其小的元素
当 6 出栈时，5 成为新的栈顶，那么 5 就是 6 左边第一个比 6 小的元素。
stackst; for(int i = 0; i < nums.size(); i++) { while(!st.empty() && st.top() > nums[i]) { st.pop(); } st.push(nums[i]); }
对于一个高度，如果能得到向左和向右的边界
那么就能对每个高度求一次面积
遍历所有高度，即可得出最大面积
使用单调栈，在出栈操作时得到前后边界并计算面积
int largestRectangleArea(vector& heights) { int ans = 0; vector st; heights.insert(heights.begin(), 0); heights.push_back(0); for (int i = 0; i < heights.size(); i++) { while (!st.empty() && heights[st.back()] > heights[i]) { int cur = st.back(); st.pop_back(); int left = st.back() + 1; int right = i - 1; ans = max(ans, (right - left + 1) * heights[cur]); } st.push_back(i); } return ans; }
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
left, right, stack = [0] * n, [n] * n, []
for i in range(n):
while stack and heights[stack[-1]] >= heights[i]:
right[stack.pop()] = i
left[i] = stack[-1] if stack else -1
stack.append(i)
ans = max((right[i] - left[i] - 1) * heights[i] for i in range(n)) if n > 0 else 0
return ans
907. 子数组的最小值之和
Leetcode
class Solution {
public int sumSubarrayMins(int[] arr) {
long res = 0L;
for (int i = 0; i < arr.length; i++){
int min = arr[i];
for (int j = i; j < arr.length; j++){
min = Math.min(min, arr[j]);
res += min;
res %= 1000000007; // 过 78 个
// if (res > 1000000007) res -= 1000000007; // 过 83 个
}
}
return (int)res % 1000000007;
}
}
单调栈 + 贡献值
数组中每个元素 E = A[i] 作为最小值的范围 (L, R) ，子数组个数为 count = (i - L) * (R - i )，元素 E 的总贡献值为 A[i] * count。计算出每个元素的贡献值，然后求和。
以 E 为中心向左右扩展，分别找第一个比 E 小的数，下标分别为 L， R。下一个更小/更大的数问题通用解法即为单调栈。
class Solution {
private static final int MOD = 1000000007;
public int sumSubarrayMins(int[] arr) {
int n = arr.length;
int[] left = new int[n], right = new int[n]; // 每个元素辐射范围的左、右边界
Deque stack = new LinkedList<>();
// 所有元素的左边界
for (int i = 0; i < n; i++) {
// 向左找第一个小于等于 E 的元素
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) { // 注意 >
stack.pop();
}
left[i] = stack.isEmpty() ? -1 : stack.peek(); // 没有左边界设为 -1
stack.push(i); // 下标入栈
}
stack.clear();
// 所有元素的右边界
for (int i = n - 1; i >= 0; i--) {
// 向右找第一个小于 E 的元素
while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
stack.pop();
}
right[i] = stack.isEmpty() ? n : stack.peek(); // 设立一个最右边界n
stack.push(i);
}
// 计算贡献值
long ans = 0L;
for (int i = 0; i < n; i++) {
ans += (long)(i - left[i]) * (right[i] - i) * arr[i]; // 强转
ans %= MOD;
}
return (int)ans;
}
}
注意⚠️：在计算左右边界时将 一侧 求解小于等于 E 的元素，解决重复元素（比如[3,1,2,4,1] 中有两个1）。
将每个大于当前元素 A[i] 的元素出栈以向左求解得到第一个小于 A[i] 的元素，那么反过来针对每个出栈的元素，当前元素 A[i] 不就是向右比它更小的第一个元素吗？这就得到了右边界。正序与逆序的关系。
每个大于当前元素 A[i] 的元素都会依次出栈，那么每个入栈元素的栈内相邻的下一个元素不就是向左比它更小的第一个元素吗？这就得到了左边界。
class Solution {
private static final int MOD = 1000000007;
// 重写根据下标取值方法，-1 和 n 返回 MIN_VALUE
private int getElement(int[] arr, int n, int i) {
if (i == -1 || i == n) return Integer.MIN_VALUE;
return arr[i];
}
public int sumSubarrayMins(int[] arr) {
int n = arr.length;
long ans = 0;
Deque stack = new LinkedList<>();
// 将下标 -1 和 n 作为两个哨兵元素，它们对应的元素为 MIN_VALUE
// -1 作为最左边界，n 作为最右边界
for (int i = -1; i <= n; i++) {
// 向左寻找第一个小于等于 A[i] 的元素
while (!stack.isEmpty() && getElement(arr, n, stack.peek()) > getElement(arr, n, i)) {
// A[cur] 就是之前思路中的 A[i]，注意区分和上面代码的区别
// 对于每个出栈元素来说，i就是它们的右边界，而栈顶元素就是左边界
int cur = stack.pop();
// 计算贡献值
ans += (long)(cur - stack.peek()) * (i - cur) * arr[cur];
ans %= MOD;
}
stack.push(i);
}
return (int)ans;
}
}
