单调栈
1.对于数组 i 位置而言, 可以以 O(n) 的时间复杂度找到左边第 1 个比当前元素 i 更大/更小的元素, 或者找到右边第 1 个比当前元素更大/更小的元素
2.先以找右边第 1 个更大的元素为例子找元素, 感受一下这个数据结构的设计思想: 对于数组中任意一个数 nums[i], 其实我们想象就是期望把右边所有元素以某种形式存储出来, 但是我们只关心和 nums[i] 最近更大的是哪个, 因为涉及到模拟 [最近] 这种时序关系, 所以用栈实现; 同时如果栈里面是单调的, 那么找第一个更大的栈顶就是最近的 & 更大的; 因此我们对于每个元素而言, 持续把不更大的栈顶弹出出去, 剩下的就是 nums[i] 右侧第一个更大的
3.这种栈的单调性是怎么保持的呢 ? 因为我们每次弹出栈顶的都是相比当前位置元素 nums[i] 更小的, 栈内剩下的都是更大的, 然后再将当前元素 nums[i] 放入进去, 所以能保持一种单调性
4.上面的解释通过阅读比较难懂, 找个例子感受下容易理解怎么做这件事:
对于一个数组 [2,1,5,6,2,3], 返回这个数组每个元素对应的右侧第 1 个比它大的元素? 没有更大的元素返回 -1
比如对于 [2,1,5,6,2,3] 这个数组, 从右往左遍历入栈, 栈内每次弹出的都是比 nums[i] 更小 (或相等) 的元素, 剩下栈顶是比 nums[i] 大的元素
vector<int> rightGreaterElement(vector<int>& nums) {
int len = nums.size();
vector<int> ans(len);
stack<int> s;
for (int i = len-1; i >= 0; --i) {
while (!s.empty() && nums[i] >= nums[s.top()]) {
// 弹出的都是栈内比 nums[i] 小或者相等的, 剩下的栈顶就是第 1 个比 nums[i] 大的
s.pop();
}
ans[i] = s.empty() ? -1 : nums[s.top()];
s.push(i);
}
return ans;
}
对于 3, 栈为空, 返回 -1, 栈内 3
对于 2, 2 没有比栈顶大, 返回栈顶 3, 栈内 3, 2
对于 6, 6 比栈顶2大, 弹出 2，弹出 3, 栈空 返回 -1, 栈内 6
对于 5, 5 没有比栈顶大, 返回栈顶 6, 栈内 6, 5
对于 1, 1 没有比栈顶大, 返回栈顶 5, 栈内 6, 5, 1
对于 2, 2 比栈顶1 大, 弹出1, 返回栈顶 5, 栈内 6, 5, 2
这个过程中, 我们发现栈里面始终保持着单调的结构, 这就是单调栈这个起名的由来, 只有这样我们才能始终拿到第 1 个比当前元素更大的
同理对于 [2,1,5,6,2,3] 这个数组, 我们找右侧第 1 个比它小的元素, 从右往左遍历入栈, 栈内每次弹出的都是比 nums[i] 更大 (或相等) 的元素, 剩下的栈顶是比 nums[i] 小的元素
对于 3, 栈为空, 返回-1，栈内 3
对于 2, 2 没有比栈顶大, 返回栈顶 3, 栈内 3, 2
对于 6, 6 比栈顶大, 弹出 2, 弹出 3, 栈空返回-1, 栈内 6
对于 5, 5 比栈顶小, 返回栈顶 6, 栈内 6, 5
对于 1, 1 比栈顶小, 返回栈顶 5, 栈内 6, 5, 1
对于 2, 2 比栈顶大, 弹出 1, 返回栈顶 5, 栈内 6, 5, 2
同理对于任意数组, 我们找左侧第 1 个比它大的元素, 从左往右遍历入栈, 栈内每次弹出的时候比 nums[i] 更小 (或相等) 的元素, 剩下的栈顶是比 nums[i] 大的元素
同理对于任意数组, 我们找左侧第 1 个比它小的元素, 从左往右遍历入栈, 栈内每次弹出的时候比 nums[i] 更大 (或相等) 的元素, 剩下的栈顶是比 nums[i] 小的元素
再总结一下,
找左侧第 1 个比它大的元素, 左往右遍历, 弹出较小 (或相等) 栈顶;
找左侧第 1 个比它小的元素, 左往右遍历, 弹出较大 (或相等) 栈顶;
找右侧第 1 个比它大的元素, 右往左遍历, 弹出较小 (或相等) 栈顶;
找右侧第 1 个比它小的元素, 右往左遍历, 弹出较大 (或相等) 栈顶;
再总结一下, 8个字: 弹小留大, 弹大留小
496.下一个更大元素 I
nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
示例 1：输入：nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出：[-1,3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：
- 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
- 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
- 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
示例 2：输入：nums1 = [2,4], nums2 = [1,2,3,4]. 输出：[3,-1]
解释：nums1 中每个值的下一个更大元素如下所述：- 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
- 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
1.对于一个数组的情况时, 如何返回该数组右侧第一个比它大的元素? 从右向左单调栈, 弹出较小栈顶实现;
vector<int> nextGreaterElement(vector<int>& nums) {
int len = nums.size();
vector<int> ans(len);
stack<int> s;
for (int i = len-1; i >= 0; --i) {
while (!s.empty() && nums[i] >= nums[s.top()]) {
s.pop();
}
ans[i] = s.empty() ? -1 : nums[s.top()];
s.push(i);
}
return ans;
}
2.我们在 nums2 找右边第1个比它大的元素, 然后记录下来, 比如用 hash 表保存下第 1 个更大位置, 然后再填充到 nums1 对应的答案数组里面;
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
int len2 = nums2.size();
stack<int> s;
unordered_map<int, int> hash;
// 从右向左遍历 nums2, 用单调栈找右边第一个更大的元素
for (int i = len2 - 1; i >= 0; --i) {
while (!s.empty() && nums2[i] >= nums2[s.top()]) {
s.pop();
}
// 记录下来右边第一个更大位置
hash[nums2[i]] = s.empty() ? -1 : nums2[s.top()];
s.push(i);
}
vector<int> ans(nums1.size());
// 还原回去对应在 nums1 中的元素的答案
for (int i = 0; i < nums1.size(); ++i) {
ans[i] = hash[nums1[i]];
}
return ans;
}
};
739.每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1: 输入: temperatures = [73,74,75,71,69,72,76,73] 输出: [1,1,4,2,1,1,0,0]
示例 2: 输入: temperatures = [30,40,50,60] 输出: [1,1,1,0]
示例 3: 输入: temperatures = [30,60,90] 输出: [1,1,0]
分析:
1.对于每天温度数组来说, 用单调栈找数组中每个元素的右边第 1 个比它大的位置, 返回 target_idx - i;
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
int len = temperatures.size();
vector<int> ans(len);
stack<int> s;
for (int i = len-1; i >= 0; --i) {
while (!s.empty() && temperatures[i] >= temperatures[s.top()]) {
s.pop();
}
ans[i] = (!s.empty()) ? s.top() - i : 0;
s.push(i);
}
return ans;
}
};
84.柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。
示例 1: 输入：heights = [2,1,5,6,2,3] 输出：10 解释：最大的矩形为图中红色区域，面积为 10
分析:
1.最大矩形是怎么来的 ？对于 位置 i 来说, 高度为 height[i], 我们用从中间到两边扩展的思想去以 height[i] 为高, 看看最大能拓宽的宽有多宽, 然后用 拓宽到极限的宽 height[i] = 最大的面积
2.假设从 i 开始, 向左侧延伸连续 >= heights[i] 到最后一个位置 left, 以及找到 i 位置向右延伸到的最后一个 >= height[i] 的位置 right, 那么最大面积的就是 (right - left + 1) height[i]; 根据这个思路, 有暴力解法;
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int len = heights.size();
int ans = 0;
for (int i = 0; i < len; ++i) {
int curHeight = heights[i];
int left = i;
int right = i;
// 以 height[i] 的高度向左边扩展
while (left - 1 >= 0 && heights[left - 1] >= curHeight) {
--left;
}
// 以 height[i] 的高度向右边扩展
while (right + 1 <= len - 1 && heights[right + 1] >= curHeight) {
++right;
}
ans = max(ans, curHeight * (right - left + 1));
}
return ans;
}
};
2.找延伸最大的过程, 也相当于我们想找到左侧第 1 个 < heights[i] 的位置 left, 以及找到 i 位置右边第 1 个 < height[i] 的位置 right, 那么最大面积的就更新为 (right - left - 1) height[i];
3.因此我们可以用单调栈是实现这样的找寻过程, 但是还要处理一下左边右边都可能出现的找不到的情况, 比如 [3,2,1,2,3], 我们找 index = 2 这个位置上的最大面积, 这种情况下应该怎么计算最大面积?
4.边界条件, 对于第 i 个元素, 左边没有任何比它小的元素的情况下, 我们用 -1 表示这个位置; 对于右侧而言, 用 len 表示找不到这个位置, 这样的话就兼容适配 (right - left - 1) height[i] 这个最大面积公式;
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int len = heights.size();
int ans = 0;
vector<int> left(len); // 保存位置 i 左边第 1 个 < height[i] 的位置, 不存在填写 -1
vector<int> right(len); // 保存位置 i 右边第 1 个 < height[i] 的位置, 不存在填写 len
stack<int> stk;
for (int i = 0; i < len; ++i) {
while (!stk.empty() && heights[stk.top()] >= heights[i]) {
stk.pop();
}
left[i] = stk.empty() ? -1 : stk.top();
stk.push(i);
}
stk = stack<int>();
for (int i = len-1; i >= 0; --i) {
while (!stk.empty() && heights[stk.top()] >= heights[i]) {
stk.pop();
}
right[i] = stk.empty() ? len : stk.top();
stk.push(i);
}
for (int i = 0; i < len; ++i) {
ans = max(ans, heights[i] * (right[i] - left[i] - 1));
}
return ans;
}
};
503.下一个更大元素 II
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。示例 1: 输入: nums = [1,2,1] 输出: [2,-1,2] 解释: 第一个 1 的下一个更大的数是 2;数字 2 找不到下一个更大的数; 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
示例 2: 输入: nums = [1,2,3,4,3] 输出: [2,3,4,-1,4]
分析:
1.下一个更大的元素带循环数组搜索的版本
```
## 42.接雨水
> 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
> 示例 1：输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
>
> 示例 2：输入：height = [4,2,0,3,2,5] 输出：9
``` cpp
class Solution {
public:
int trap(vector<int>& height) {
}
};
962.最大宽度坡
给定一个整数数组 A，坡是元组 (i, j)，其中 i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。
找出 A 中的坡的最大宽度，如果不存在，返回 0 。
示例 1：输入：[6,0,8,2,1,5] 输出：4 解释： 最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.示例 2：输入：[9,8,1,0,1,9,4,0,4,1] 输出：7 解释：最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1.
分析:
1.对每个位置上的元素, 找右侧位置比它大的最多的一个元素; 暴力可做
2.单调栈做法, 栈里面保存一个严格递减的最长序列, 然后从右往左遍历数组, 和栈顶元素作比较计算最大宽度
class Solution {
public:
int maxWidthRamp(vector<int>& nums) {
int len = nums.size();
int ans = 0;
stack<int> s;
// 栈里面存一个严格单调递减的最长序列
for (int i = 0; i < len; ++i) {
if (s.empty() || nums[s.top()] > nums[i]) {
s.push(i);
}
}
// 倒序遍历数组更新最大坡度
for (int i = len-1; i >= 0; --i) {
while (!s.empty() && nums[s.top()] <= nums[i]) {
int pos = s.top();
s.pop();
ans = max(ans, i - pos);
}
}
return ans;
}
};
转载请注明来源, from goldandrabbit.github.io
